Data Structure - Heap
A heap is a special complete binary tree structure that satisfies the heap-order property. A heap only guarantees the size relationship between parent and child nodes, and does not require a strict order between left and right subtrees.
Definition and Storage of Heap
Heap - Max Heap Structure and Array Storage
Tree View (Max Heap)
15Index 0
10Index 1
8Index 2
53
34
25
Array View (Compact Storage)
15
[0]10
[1]8
[2]5
[3]3
[4]2
[5]Parent: (i-1)/2 | Left child: 2i+1 | Right child: 2i+2
Complete binary tree → naturally suited for arrays, no pointer overhead
Sift Up (Insertion) O(log n)
Place new element at the end → compare with parent → swap if larger → repeat to the top of the heap
Sift Down (Delete Root) O(log n)
Move the last element to the root → compare with the larger child → swap if smaller → repeat until leaf
Two types of heaps:
- Max HeapEach parent node ≥ child node, root node is the maximum value
- Min HeapEach parent node ≤ child node, root node is the minimum value
Since a heap is a complete binary tree, it is naturally suited for array storage:
| Node (index i) | Relationship | Position (0-based) |
|---|---|---|
| Parent node | parent(i) | (i - 1) / 2 |
| Left child node | left(i) | 2 * i + 1 |
| Right child node | right(i) | 2 * i + 2 |
Heap Insertion and Deletion (Heapify Process)
Example
#include <stdio.h>
#define MAX 100
/* Max Heap Structure */
struct MaxHeap {
int arr[MAX];
int size; /* Current number of elements */
};
void initHeap(struct MaxHeap* h) { h->size = 0; }
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Sift Up: adjust the newly inserted element from bottom to top
Compare with the parent node; if greater than the parent, swap; repeat until heap order is satisfied */
void siftUp(struct MaxHeap* h, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (h->arr[idx] <= h->arr[parent]) break;
swap(&h->arr[idx], &h->arr[parent]);
idx = parent;
}
}
/* Insertion: first place the element at the end, then adjust using sift-up O(log n) */
void insert(struct MaxHeap* h, int value) {
if (h->size >= MAX) return;
h->arr[h->size] = value;
siftUp(h, h->size);
h->size++;
}
/* Sift Down: adjust from the root downward
Compare with the larger child node; if smaller, swap; repeat until heap order is satisfied */
void siftDown(struct MaxHeap* h, int idx) {
while (1) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < h->size && h->arr[left] > h->arr[largest])
largest = left;
if (right < h->size && h->arr[right] > h->arr[largest])
largest = right;
if (largest == idx) break;
swap(&h->arr[idx], &h->arr[largest]);
idx = largest;
}
}
/* Delete root (maximum value): move the last element to the top, then adjust using sift-down O(log n) */
int extractMax(struct MaxHeap* h) {
if (h->size == 0) return -1;
int maxVal = h->arr[0];
h->arr[0] = h->arr[--h->size]; /* Move last element to top */
siftDown(h, 0); /* Sift down adjustment */
return maxVal;
}
int main() {
struct MaxHeap h;
initHeap(&h);
int vals[] = {3, 10, 5, 8, 2, 15};
for (int i = 0; i < 6; i++) insert(&h, vals[i]);
printf("Take out maximum values in sequence: ");
while (h.size > 0) {
printf("%d ", extractMax(&h));
}
printf("\n"); /* Output: 15 10 8 5 3 2 (descending order) */
return 0;
}
#define MAX 100
/* Max Heap Structure */
struct MaxHeap {
int arr[MAX];
int size; /* Current number of elements */
};
void initHeap(struct MaxHeap* h) { h->size = 0; }
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Sift Up: adjust the newly inserted element from bottom to top
Compare with the parent node; if greater than the parent, swap; repeat until heap order is satisfied */
void siftUp(struct MaxHeap* h, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (h->arr[idx] <= h->arr[parent]) break;
swap(&h->arr[idx], &h->arr[parent]);
idx = parent;
}
}
/* Insertion: first place the element at the end, then adjust using sift-up O(log n) */
void insert(struct MaxHeap* h, int value) {
if (h->size >= MAX) return;
h->arr[h->size] = value;
siftUp(h, h->size);
h->size++;
}
/* Sift Down: adjust from the root downward
Compare with the larger child node; if smaller, swap; repeat until heap order is satisfied */
void siftDown(struct MaxHeap* h, int idx) {
while (1) {
int largest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < h->size && h->arr[left] > h->arr[largest])
largest = left;
if (right < h->size && h->arr[right] > h->arr[largest])
largest = right;
if (largest == idx) break;
swap(&h->arr[idx], &h->arr[largest]);
idx = largest;
}
}
/* Delete root (maximum value): move the last element to the top, then adjust using sift-down O(log n) */
int extractMax(struct MaxHeap* h) {
if (h->size == 0) return -1;
int maxVal = h->arr[0];
h->arr[0] = h->arr[--h->size]; /* Move last element to top */
siftDown(h, 0); /* Sift down adjustment */
return maxVal;
}
int main() {
struct MaxHeap h;
initHeap(&h);
int vals[] = {3, 10, 5, 8, 2, 15};
for (int i = 0; i < 6; i++) insert(&h, vals[i]);
printf("Take out maximum values in sequence: ");
while (h.size > 0) {
printf("%d ", extractMax(&h));
}
printf("\n"); /* Output: 15 10 8 5 3 2 (descending order) */
return 0;
}
Application Scenarios
| Scenario | Description |
|---|---|
| Priority Queue | The heap is the most common underlying implementation of a priority queue |
| Heap Sort | O(n log n) in-place sorting algorithm (detailed in Chapter 18) |
| Top K Problem | Use a min heap to maintain the top K largest elements |