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:

     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