Min Heap vs. Max Heap

Min and Max heaps are complete binary trees with some unique properties.

Binary Tree

A Binary Tree is a tree data structure wherein each node has at most two “children.”

A node in the binary tree typically contains the following properties:

• Reference to the left child.
• Reference to the right child.
• Data

A complete Binary Tree is a binary tree in which every level, except possibly the last, is filled.

How are Min/Max Heaps represented?

A Min/Max heap is typically represented as an array.

• Arr[0] Returns the root node.
• 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.

Time Complexity of Min/Max Heap

• Get Max or Min Element

  • The Time Complexity of this operation is O(1).

• Remove Max or Min Element

  • The time complexity of this operation is O(Log n) because we need to maintain the max/mix at their root node, which takes Log n operations.

• Insert an Element

  • Time Complexity of this operation is O(Log n) because we insert the value at the end of the tree and traverse up to remove violated property of min/max heap.