Heap Tree

Heap is a complete binary tree based data structure that satisfies heap property.

Heap Property :

• Min Heap = each node’s element is smaller than its children’s node.
  • It implies that the smallest element is located at the root of the tree.
  • The largest element is located somewhere at one of the leaves node.
  • Insertion in min heap :
    • We would like to insert a new element into the heap, but we should maintain its heap property.
    • Insert the new element at the end of the heap (after the index of the last element).
    • Upheap the new element (fixing its heap property).
  • Deletion in min heap :
    • Here we only concern with deletion of the smallest element which is located at the root.
    • Replace root with the last element of the heap.
    • Decrease the number of element in heap.
    • Downheap root (fixing its heap property).
• Max Heap = each node’s element is larger than its children’s.
  • Each node’s element is larger than its children’s element.
  • It implies that the largest element is located at the root of the tree
  • Max-heap holds the same principle as min-heap and can be used to create priority queue which need to find the largest element instead of the smallest one.
• Min Max Heap :
  • The heap condition alternates between minimum and maximum level to level
  • Each element on even/odd level are smaller than all its children (min-level).
  • Each element on odd/even level are larger than all its children (max-level).The purpose of min-max heap is to allow us to find both the smallest and the largest element of the heap at the same time.
  • The smallest element is located at the root.
  • The largest element is located in one of the root’s child (either left/right child).
  • Note: the largest element may be located at root if there is only one element in the heap.
  • Insertion :
    • Insert the new element at the end of the heap (after the index of the last element).
    • Upheap the new element (fixing its heap property).
    • Upheap in min-max heap is a bit different with min-heap or max-heap.
  • Deletion :
    • Deletion MIN
      • Replace root with the last element in heap.
      • Decrease the number of element in heap.
      • Downheapmin from root.
    • Deletion MAX :
      • Replace either left-child or right child of root (depends on which one is larger) with the last element in heap.
      • Decrease the number of element in heap.
      • Downheapmax from the node.