heap is a specialized tree-based data structure that
satisfied the heap property:
Applications: A heap has many applications, including the most efficient implementation of priority queues, which are useful in many applications. In particular, heaps are crucial in several efficient graph algorithms.
Binary heap storage rules -- A heap implemented with a binary tree in which the following two rules are followed:
Example: which one is a heap?
Adding an Element to a Heap
Example: We want to insert a node with value 42 to the heap on the left.
The above process is called reheapification upward.
Pseudocode for Adding an Element:
Removing the Root of a Heap
The procedure for deleting the root from the heap -- effectively extracting the maximum element in a max-heap or the minimum element in a min-heap.
The above process is called reheapification downward.
Psuedocode for Removing the Root:
Now, think about how to build a heap. Check out the example of inserting 27, 35, 23, 22, 4, 45, 21, 5, 42 and 19 to an empty heap.
A more common approach is to store the heap in an array. Since heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by simple arithmetic on array indices.
The rules (assume the root is stored in arr):
This implementation is particularly useful in the heapsort algorithm, where it allows the space in the input array to be reused to store the heap (i.e., the algorithm is in-place). However it requires allocating the array before filling it, which makes this method not that useful in priority queues implementation, where the number of elements is unknown.
It is perfectly acceptable to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element. Here's a method we can follow.
|Building a Heap|
A heap could be built by successive insertions. This approach requires O(n log n)
time for n elements. Why?
The optimal method:
As an example, let's build a heap with the following values: 20, 35, 23, 22, 4, 45, 21, 5, 42 and 19. Click here to see the process.
As has been proved here, this optimal method requires O(n) time for n elements.
A priority queue behaves much like an ordinary queue:
Heap Implementation of P.Q.
In the heap implementation of a priority queue, each node of the heap contains one element along with the element's priority, and the tree is maintained so that it follows the heap storage rules using the element's priorities to compare nodes:
A P.Q. Implementation Using an Ordinary Queue