Problem Statement
What type of tree is a heap?
Explanation
A heap is a complete binary tree where all levels are fully filled except possibly the last level, which is filled from left to right. This structure allows efficient array representation and maintains heap properties.
Complete binary trees ensure that the height is always log n, making heap operations like insert and delete efficient. The array representation is space-efficient with no wasted slots, and parent-child relationships can be calculated using simple formulas: parent at index i divided by 2, left child at 2 times i, and right child at 2 times i plus 1. This is why heaps are preferred for implementing priority queues.
Code Solution
SolutionRead Only
// Heap as Complete Binary Tree
// 90 (index 0)
// / \
// 80 70 (indices 1, 2)
// / \ /
// 60 50 40 (indices 3, 4, 5)
// Array representation: [90, 80, 70, 60, 50, 40]
// Index calculations:
// Parent of node i: (i-1)/2
// Left child of node i: 2*i + 1
// Right child of node i: 2*i + 2
class MaxHeap {
int[] heap;
int size;
int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }
}
// Why complete binary tree?
// - Efficient array representation
// - Height always log(n)
// - No wasted spacePractice Sets
This question appears in the following practice sets:
