Heap Sort - Binary Heaps
Binary Heaps
A binary heap is a complete binary tree that satisfies the heap property.
Heap Property
Max Heap: Parent ≥ Children (for all nodes) Min Heap: Parent ≤ Children (for all nodes)
For heap sort, we use a max heap.
Array Representation
Heaps are stored in arrays. For a node at index i:
- Left child: 2i + 1
- Right child: 2i + 2
- Parent: ⌊(i-1)/2⌋
Visual Example
Interactive Diagram
This interactive diagram requires JavaScript to be enabled.
Steps:
- Binary heap as a tree structure
- Same heap stored in an array
Complete Binary Tree
A complete binary tree is filled from left to right at each level. This allows efficient array storage.
Heap Operations
• Add element at end
• Bubble up to maintain heap property
• O(log n) time
• Remove root (max element)
• Move last element to root
• Heapify down
• O(log n) time
• Maintain heap property
• Compare with children
• Swap if needed
• O(log n) time
What’s Next?
Now that you understand heaps, let’s learn the heapify operation.
Progress 29%
Page 2 of 7
← Previous
→ Next
Discussion
Loading comments...