Heap, priority queue, heapify, heapsort
The (binary) heap data structure is an array object that can be viewed as a complete binary tree (see Section 5.5.3), as shown in Figure 7.1. Each node of the tree corresponds to an element of the array that stores the value in the node.
Complexity :
The HEAPSORT procedure takes time O(n lg n)
since the call to BUILD-HEAP takes time O(n) and
each of the n - 1 calls to HEAPIFY takes time O(lg n).
MAXIMUM implements the MAXIMUM operation in T(1) time.
PARENT(i)
return ?i/2?
LEFT(i)
return 2i
RIGHT(i)
return 2i + 1
• Two kinds of binary heaps : max-heap, min-heap
For every node i other than root,
A[PARENT(i)] >= A[i] - maxHeap
A[PARENT(i)] <= A[i] - minHeap
· Building Heap :
Popular Application of heap : Priority queues
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. there are two kinds of priority queues: max-priority queues and min-priority queues.
In min priority queue the find operation finds element with minimum priority, while delete operation deletes this element. Vice versa.
Implementation : STL priority queue, Heap sort
AbstractDataType MaxPriorityQueue{
Instances
Finite collection of elements, each has priority
Operations
Create( ) :create an empty priority queue
Size( ) : return number of elements in the queue
Max( ) : return element with maximum priority
Insert(x) : insert x into queue
DeleteMax(x): delete the element with largest priority from queue
A priority queue supports the following operations.
INSERT(S, x) inserts the element x into the set S. This operation could be written as S S {x}. The time required to do the insertion could be as much as O(Height) = O(log N)
Insertion is implemented by creating a hole at the next available location and then percolating it up until the new item can be placed in it without introducing a heap- order violation with the hole's parent.
This general strategy is called percolate up, in which insertion is imple- mented by creating a hole at the next available location and bubbling it up the heap until the correct location is found. Figure 21.9 shows the insert method, which implements the percolate up strategy by using a very tight loop.
MAXIMUM(S) returns the element of S with the largest key.
EXTRACT−MAX(S) removes and returns the element of S with the largest key The procedure HEAP-
DeleteMin(X) makes single pass from root down towards leaf. Take O(height) = O(log n)
The deleteMin operation is handled in a similar manner to the insert operation. As shown already, finding the minimum is easy; the hard part is removing it. When the minimum is removed, a hole is created at the root. The heap now becomes one size smaller, and the structure property tells us that the last node must be eliminated. Fig 21.10 shows the situation: The minimum item is 13, the root has a hole, and the former last item needs to be placed in the heap somewhere.
HEAP-MAXIMUM(A)
1 return A[1]
Applications
Machine scheduling - One application of priority queues is to schedule jobs on a shared computer. The priority queue keeps track of the jobs to be performed and their relative priorities. When a job is finished or interrupted, the highest-priority job is selected from those pending using EXTRACT-MAX. A new job can be added to the queue at any time using INSERT
A priority queue can also be used in an event-driven simulator. The items in the queue are events to be simulated, each with an associated time of occurrence that serves as its key. The events must be simulated in order of their time of occurrence, because the simulation of an event can cause other events to be simulated in the future. For this application, it is natural to reverse the linear order of the priority queue and support the operations MINIMUM and EXTRACT-MIN instead of MAXIMUM and EXTRACT-MAX. The simulation program uses EXTRACT-MIN at each step to choose the next event to simulate. As new events are produced, they are inserted into the priority queue using INSERT.
Huffman codes – lossless compression
