A Heap Based Priority Queue
By Sriranga Veeraraghavan
CS 161 Stanford University Summer 1998
9 August 1998
1.0 IntroductionFor this project, I have implemented the specified scheduler framework based on the Heap data structure as described by Cormen, Leierson and Rivest[1] and Segdewick[2]. The Heap was chosen for its simplicity, easy of maintenance and reasonable efficiency.
I have worked alone on this project.
1.1 SourcesThe source files for this project are:
2.0 Description
The data structure used in this scheduler implementation is known as a Binary Heap. This data structure was first described by Williams[3], who described an implementation of a priority queue based on this structure.
My implementation is partially based on descriptions of the heap operations given by Cormen, Leierson and Rivest [1] and Segdewick[2], but the following operations were independently implemented:
As discussed latter, my implementations fulfill the O(lg(n)) worst case running time requirement specified by Cormen, Leierson and Rivest[1].
In this implementation the heap is represented as a structure which holds three key pieces of information:
As specified, the max heap size is determined at run time based on user input. The nodes in the heap are treated as if they were in an array of the max size and are accessed based on an index. Each node holds essential information about the process it represents which include:
The nodes are stored in the heap with their priority as the key. Thus the node (or job) with the highest priority will always be the top most node.
2.1 Priority Queue Operations
The following priority queue operations have been implemented:
I will discuss the implementation and running time of each operation in turn.
2.1.1 Insert
The heap insert operation is implemented exactly as described by Cormen, Leierson and Rivest[1].
The only modification is that the
compare_priority() function is used to compare the priorities of a node and its parent in place of a direct comparison. This function is a wrapper around the provided library routine compare(), and is required because we need to know only if a given key is greater than another key. If two processes have equal priority, then their relative ordering is based on which process has the greater job id.The running time of this operation is worst case O(lg(n)). This running time occurs when a newly added node has a greater priority than every other node in the heap. When such a node is added, it must be moved from its position as the last element in the heap to the first, by tracing a path from its current position to the root of the heap. Since this path contains at most lg(n) nodes the worst case running time is O(lg(n)).
2.1.2 Delete
The heap delete operation in my implementation is loosely based on the function HEAP_EXTRACT_MAX given by Cormen, Leierson and Rivest[1]. The process is as follows:
HEAP_DELETE(A,i) {
if (i > heap_size(A) || i < 1)
error "No such element";
A[i] = A[heap_size(A)];
heap_size(A)--;
heapify(A,i);
}
In order to remove the requested item, we move the last item in the heap to the position of the item to be deleted. Once this operation completes, the requested item has been deleted from the heap allowing us to shorten the heap size by 1. At this point the heap property may be violated so we call
heapify() to restore this property. The heapify() function is implemented as given by Cormen, Leierson and Rivest[1], except for the previously noted change involving compare_priority().The running time of this operation is bounded by the call to
heapify(). The process of checking the element, moving the last element to the index of the item to be deleted and shortening the heap only constant time, Q(1). The call to heapify(), will require O(lg(n)) in the worst case, thus the running time of this routine is O(Q(1) + O(lg(n)) = O(lg(n)). This satisfies the worst case running time requirement imposed by Cormen, Leierson and Rivest[1].2.1.3 Increase Key
My implementation of the increase key operation exhibits similarities to the delete operation. A short description of a key change operation is given by Segdewick[2], but it requires uses extra comparisons between keys to implement. My process is as follows:
HEAP_INCREASE_KEY(A,i,key) {
if (i > heap_size(A) || i < 1)
error "No such element";
A[i] = key;
heapify(A,i);
}
Here we set the key at the specified node to be given key, and then we call
heapify() to restore any violations of the heap property.This routine assumes that the specified key is greater than the value currently stored at the index i. The scheduler specification stated that this assumption would always hold true.
The worst case running time of this routine is bounded by the call to
heapify(). The error checking and the key assignment both require only constant time, Q(1). The call to heapify(), will require O(lg(n)) in the worst case, thus the running time of this routine is O(Q(1) + O(lg(n)) = O(lg(n)). This satisfies the worst case running time requirement imposed by Cormen, Leierson and Rivest[1].2.1.4 Maximum
The maximum operation is implemented to return a pointer to the first node in the heap. If the heap is empty it returns a null pointer. Since this operation requires only one access it runs in constant time, Q(1).
2.1.5 Extract Maximum
The extract maximum operation is implemented to return the topmost node and then restore the heap property using
heapify(). My implementation is the same as the one given by Cormen, Leierson and Rivest[1].In this routine the call to
heapify() dominates, requiring O(lg(n)) in the worst case. The running time of this is bounded by this and is thus O(lg(n)).2.2 Best and Worst Case Inputs
The heap is an extremely efficient data structure. It is reasonably fast, since none of its operations require more than O(lg(n)) worst case time.
In my implementation all of the operations display this behavior, but there are hidden costs involved with the following commands that could cause slow performance:
2.2.1 KILL and NICE
Both the KILL and NICE operations are really bounded by O(n + lg(n)) and not O(lg(n)). Although it is possible to delete or increase the key of any node from the heap and restore the heap property in O(lg(n)), these commands request that a node with a particular job id be acted on. In order to act on the specified node, it must be found in the heap.
This involves searching the array in which the nodes are stored for a node with the given job id. The worst case occurs when the search fails or when the requested job id belongs to the last item in the array. These conditions can only occur after all n nodes in the array have been considered, thus the find operation has a O(n) worst case running time.
Due to this fact both the KILL and NICE commands can be slow. If a search fails these commands have Q(n) running time, but if a search succeeds, then the commands can have a worst case running time of O(n + lg(n)). Inputs that always perform KILL or NICE operations on the last item in a large heap will increase the running time of scheduler.
Two schemes were considered to increase the performance of the find operation:
If a hash table were maintained then the node corresponding to a particular job id could be located in Q(1 + a) time, assuming simple uniform hashing and collision resolution via chaining. In this hash table the key would be job id for a process and the stored value would be that job’s index in the heap. Though two jobs with the same id will not run concurrently, depending on the hash function used, two jobs with different job id’s may hash the same.
The alternative to the hash table was to maintain a binary search tree of processes, where the key would be the job id and value of a particular key would be the index of the node corresponding to that job id in the heap. The binary search tree is attractive because all the operations that we will perform (search, insert and delete) run in O(h) = O(lg(n)) time. Thus we could find the index of a given job id much faster than the find method we now employ.
Both of these solutions, and indeed any solution that speeds up the find operation, slow down the entire system. This is because any change to the heap requires a change to the auxiliary structure. Thus a call to heapify(), which may touch lg(n) nodes, will require lg(n) nodes of the auxiliary structure to be updated. This fact is lost in the O notation, since the total cost of heapify() would be O(lg(n) + lg(n)) = O(lg(n). In reality, the constants will be significant.
To justify implementing either scheme, the majority of inputs (> lg(n)) would have to be NICE or KILL requests for the last node in the heap. Even in this case, the amount of extra code required for these schemes is almost as much as the code which is required to implement the scheduler itself, thus it hard to justify replacing the short and simple find routine with something much more complex, but not much more efficient.
2.2.2 Age Processes
The aging of processes every few cycles presented an opportunity for improvement. The current implementation ages each of the processes then calls the BUILD_HEAP routine described by Cormen, Leierson and Rivest[1], in order to restore the heap property. This routine requires O(n) time to run in the worst case. There is a modification to this routine, called BUILD_HEAP_PRIME< suggested by Cormen, Leierson and Rivest[1]. This modification runs in Q(n(lg(n)) time.
It is obvious that for large values of n, the standard BUILD_HEAP will be slower than BUILD_HEAP_PRIME, thus an ideal implementation would be one that switched to BUILD_HEAP_PRIME from BUILD_HEAP at some critical value of n. In order to determine this critical value, I conducted some tests to determine the constants that were hidden by the Q and O notations. Since the results of these tests were inconclusive, I have chosen not to implement a switch between these two routines.
2.3 Comparision
The primary reasons for choosing the heap as the data structure for my priority queue were:
First, of all the data structures considered, the heap was the simplest to implement and debug. Since it is a heavily studied data structure, documentation was readily available. This proved invaluable because the correctness of all the major operations could be easily verified with known examples.
In addition, each of the operations are based on simply introducing a violation of the heap property, and then using a routine to restore the heap property. This meant that once the
heapify() routine started functioning correctly, each of the other operations could be implemented in short order.Second, the heap is a very efficient data structure in terms of the running time of its operations. The major operations (HEAP_INSERT, HEAP_DELETE, HEAP_INCREASE_KEY), except BUILD_HEAP, run in O(lg(n)) time. BUILD_HEAP runs in O(n) time, but even this is quite good. Also, the heap provides instant access to the node with the highest priority. Of the other data structures available, some (eg Leftist Heaps and Fibonacii Heaps) allowed for the required operations to be performed faster, but they required more memory and were much harder to debug and verify.
The memory requirement was the third consideration. The heap provided the most compact memory image. All of the heap elements are stored adjacently in memory, and no additional space is required for moving records around. By comparison, leftist heaps provide slightly faster access but at the cost of extra memory. For large heaps, standard binomial heaps can handle the more nodes in a smaller memory. Though Fibonacii Heaps give better performance when the heap is large, they require more memory than binomial heaps, thus fewer nodes can be represented. In addition, for small heaps, the binomial heap provides on par performance, while requiring a very small memory image.
3.0 Acknowledgements
I would like to thank Bharathi Raghavan, Mark Sapsford and Lothar Groth for their invaluable assistance. I would not have been able to complete this assignment without their help in debugging and their wisdom regarding implementation details.
3.1 References