Skip to main content

Heap Fundamentals

Essential concepts and operations for working with heap data structures.

Min-heap & max-heap​

  • Min-Heap: Parent node is smaller than or equal to children
  • Max-Heap: Parent node is larger than or equal to children
  • Heap Property: Maintained for all nodes in the tree
  • Complete Binary Tree: All levels filled except possibly last level

Heap operations (insert, extract, heapify)​

  • Insert: Add new element while maintaining heap property
  • Extract: Remove and return root element
  • Heapify: Restore heap property after modification
  • Build Heap: Convert array into heap structure

Heap sort​

  • Algorithm: Sort array using heap data structure
  • Time Complexity: O(n log n) for all cases
  • Space Complexity: O(1) for in-place sorting
  • Stability: Not stable sorting algorithm

Heap implementation​

  • Array Representation: Using array to represent heap
  • Index Calculations: Parent, left child, right child indices
  • Memory Efficiency: Compact representation in array
  • Cache Performance: Good cache locality

Heap properties​

  • Height: O(log n) height for n elements
  • Insertion: O(log n) time complexity
  • Deletion: O(log n) time complexity
  • Peek: O(1) time complexity for root access