Usage
- In Heapsort
- In Priority Queue
- Not the garbage collector storage (as provided by JVM)
Definition
A binary Heap is an array object. We can view that array object as a near complete binary tree. A binary tree is said to be a complete binary tree when all the nodes except possibly for the leaves has two children.
The height of a node in a heap is defined as the number of edges on the longest simple downward path from the node to a leaf. For the element with value 22, the height is 3.
We define the height of the heap to be the height of its root. The height of heap in our example is 4.
Parent Node
For any element in array with index i, the parent of the node is i/2
Let’s consider the fourth element of the array shown in Fig. 1. The index is shown in the first row while the values are shown in the second row.
Here, index or i is 4. The parent should be i/2 or 4/2 = 2.
As we can verify in the Fig. 2, parent of the element at fourth index is indeed element at second index.
Left Child
For any element in array with index i, the left child of the node is 2 * i.
For element at fourth index, left child is the element at the eighth index which can be verified in the Fig. 2.
Right Child
For any element in array with index i, the right child of the node is 2 * i + 1.
For element at fourth index, right child is the element at the ninth index which can be verified in the Fig. 2.
Types
Max Heap
In a max-heap, the max-heap property is that for every node i other than the root,
A[Parent(i)] >= A(i)
This essentially means that the largest element in a max-heap is stored at the root, and the subtree rooted at a node contains values no larger than that contained at the node itself.
Min Heap
In a min-heap, the min-heap property is that for every node i other than the root,
A[Parent(i)] <= A(i)
This essentially means that the smallest element in a min-heap is stored at the root, and the subtree rooted at a node contains values larger or equal to that contained at the node itself.
Heap Operation
max_heapify
- Assume that the trees rooted at left(i) and right(i) are max-heaps
- If element A[i] violates the max-heap property, correct violation by “trickling” element A[i] down the tree, making the subtree rooted at index i a max-heap
Pseudocode
| max-heapify(A,i){ | |
| index_of_left_child = left(i); | |
| index_of_right_child = right(i); | |
| heap_size = number_of_elements_in_heap(A) | |
| if((index_of_left_child <= heap_size) && (A[index_of_left_child] > A[i])) | |
| largest = index_of_left_child | |
| else | |
| largest = i | |
| if((index_of_right_child <= heap_size) && (A[index_of_right_child] > A[i])) | |
| largest = index_of_right_child | |
| if(i != largest) | |
| exchange(A[i], A[largest]) | |
| max-heapify(A,largest) |
Time Complexity
O(log(n))
log(n) is also the height of the tree. Time complexity as O(log(n)) can also be seen as each level has to be accessed once.
build_max_heap(A)
To build max heap out of an unordered array, we just need to call max_heapify for all elements.
We can safely start from n/2 to 1 as the elements from 1 to n/2 are leaves.
Pseudocode
| for i=n/2 downto 1 | |
| do max_heapify(A, i) |
Time Complexity
O(n)
max_heapify takes O(1) for nodes that are the level above the leaf nodes and O(l) for the elements that are l level up the leaf.
Proof
Further Resource:
If you liked this article and would like one such blog to land in your inbox every week, consider subscribing to our newsletter: https://skillcaptain.substack.com
Leave a Reply