Heap
Heap
is a binary tree (although not a BST) with following 2 properties:
1)
Its a full binary tree i.e. all its nodes either have 2 children or
none.
2)
Every node is greater than its children. (For min-heap, every node is
smaller than its children)
Insertion
Any element to be inserted in a heap is always appended at the bottom of
the heap.
Then the element is compared with its parent.
If the parent is smaller, it is swapped with the new node.
The node is then
compared with its new parent and moves up the heap until it reaches
its correct position.
This moving up operation is called heapify
Clearly,
insertion is O(log N) operation where N is the number of nodes in the heap.
The
new node is added as deepest and rightmost leaf to keep the tree a
full binary tree.
Example:
New node added at 'x' |
Let's say '1' is added to the heap |
Due to heapify, it will move to its parent's position |
And since its still smaller, '1' will once again move |
3
/ \
7 4
/ \
8 x
|
3
/ \
7 4
/ \
8 1
|
3
/ \
1 4
/ \
8 7
|
1
/ \
3 4
/ \
8 7
|
Deletion
Deletion
from a heap is always from the top (i.e. we always remove either the
max or the min element).
After deletion, the deepest and rightmost
leaf is put at the top of the heap and it then moves down by swapping
with the bigger of its children.
Thus, deletion from a heap is also O(log N) operation where N is the number of nodes in the heap.
Data structure used
to build heap
Array Implementation
of Heap
If
we use tree like data structure (with right and left pointers) to
represent a heap, then finding the leaf node where a new node can be
inserted would not be easy. Finding the deepest and rightmost leaf
node would be O(n). Similarly when deleting, the leaf node which will
move to the top of the heap will be also O(n).
To
avoid these problems, we can use array representation of tree to
represent heap.
In
this representation, a growing array is used to store the nodes of a
tree.
Since
the tree is always fully balanced, children of node at index ‘k’
will be present at indices 2k+1 and 2k+2
With
this representation, the leaf node required for insertion/deletion is
always at the end of the array.
Also,
any number of insert/delete operations do not create any holes (empty
places between filled indices) in the array as the heap remains
balanced always.
Tree Implementation
of Heap
However,
still if there is a requirement to use tree-like structure with right
and left pointers, then the best solution is to create a list of all
the leaf nodes. Each node in the list should also contain the level
of the node. With this auxiliary data structure, one can easily find
the leaf node for insertion/deletion by seeking that node in the list
where level changes from max to max-1
|