Heap - C P P

Theory

• Basic
  • Heap is a Complete Binary Tree that comes with a heap order property
  • Implemented using Array
  • Deletion means deleting root node
• Types
  • MaxHeap => Node greater than its child nodes
  • MinHeap => Node less than its child nodes
• Tricks (for 1 based indexing)
  • node = i, parent = i/2
  • left child = 2*i + 1, right child = 2i + 2
  • Leaf Nodes from (i/2 + 1) to i index
• Heapify Algorithm
  • Time Complexity = O(logn)
  • Building a Heap takes O(n)

STL Commands

• #include <queue> => Header to include
• priority_queue<int> variable => Max heap by default
  • priority_queue<int, vector<int>, greater<int>> variable => Min heap
  • priority_queue<ClassName, vector<ClassName>> ClassName1 => User-defined Heap, Third argument is a class that has a function named operator having return type bool for comparing values
• variable.push(value) => Insert element
• variable.pop() => Remove top element
• variable.top() => Returns minimum/maximum element according to min/max heap declared
• variable.size() => Returns size of Heap
• variable.empty() => Returns true if Heap is empty