Concepts of Heap
Last updated
Last updated
A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
A Binary Heap is a Binary Tree with following properties. 1) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
2) A Binary Heap is either Min Heap or Max Heap.
Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
A Binary Heap is a Complete Binary Tree. A binary heap is typically represented as an array.
The root element will be at Arr[0].
Below table shows indexes of other nodes for the ith node, i.e., Arr[i]:
Arr[(i-1)/2]
Returns the parent node
Arr[(2*i)+1]
Returns the left child node
Arr[(2*i)+2]
Returns the right child node
1) Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nLogn) time.
2) Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time.
Heaps are mainly used for implementing priority queue.
Binomial Heap is an extension of Binary Heap that provides faster union or merge operation together with other operations provided by Binary Heap.
In terms of Time Complexity, Fibonacci Heap beats both Binary and Binomial Heaps. Like Binomial Heap, Fibonacci Heap is a collection of trees with min-heap or max-heap property.
The traversal method use to achieve Array representation is Level Order
