Binary Heap Visualization
A Binary Heap is a complete binary tree (typically stored in an array), where each node satisfies the heap property: in a max-heap, parents are greater than or equal to their children, while in a min-heap, they are less than or equal. Heap Sort utilizes this structure by building a Max-Heap and repeatedly extracting the root element to the end of the array, resulting in an efficient O(n log n) sorting algorithm. Beyond sorting, heaps are widely used to implement priority queues.
Pseudocode
function insert(value):
arr[n] = value
i = n, n = n + 1
while i > 0:
parent = (i - 1) / 2
if arr[parent] >= arr[i]:
break
swap(parent, i)
i = parent
AI Summary
(3 credits)
Common Interview Questions
How is a complete Binary Heap represented efficiently using an array without explicit child pointers?
For a parent at index i in a 0-indexed array, left child is at 2i + 1, right child is at 2i + 2, and parent is at (i - 1) / 2. This eliminates the need for explicit child pointers, reducing memory usage.
What is the time complexity of insert, extract, and peek operations in a Binary Heap?
peek(): O(1) (root element). insert(): O(log n) (heapify-up). extract(): O(log n) (replace root with last element and heapify-down).
How do you find the K largest elements in an unsorted stream of N elements efficiently?
Maintain a Min-Heap of size K. Iterate through the stream: if an element is larger than the root of the Min-Heap, replace the root and heapify. Final Min-Heap contains the K largest elements in O(N log K) time and O(K) space.
💬 Discussion
Sign in to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0