Heap

A Heap is a specialized tree-based data structure that satisfies the heap property. In a binary heap, the parent node is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children. Heaps are commonly used to implement priority queues.

Heap Visualization

Complexity

Time Complexity: O(log n) insert, O(log n) delete, O(1) peek

Space Complexity: O(n)

Pseudocode

class Heap:
  function insert(value):
    add value to the end of the array
    heapifyUp()
  
  function extractRoot():
    root = heap[0]
    move last element to root
    heapifyDown()
    return root
  
  function heapifyUp():
    while parent violates heap property:
      swap with parent
  
  function heapifyDown():
    while child violates heap property:
      swap with appropriate child