8.1 Heap¶
A heap is a complete binary tree that satisfies specific conditions and can be mainly categorized into two types, as shown in Figure 8-1.
- min heap: The value of any node \(\leq\) the values of its child nodes.
- max heap: The value of any node \(\geq\) the values of its child nodes.
Figure 8-1 Min heap and max heap
As a special case of a complete binary tree, heaps have the following characteristics.
- The bottom layer nodes are filled from left to right, and nodes in other layers are fully filled.
- We call the root node of the binary tree the "heap top" and the bottom-rightmost node the "heap bottom."
- For max heaps (min heaps), the value of the heap top element (root node) is the largest (smallest).
8.1.1 Common Heap Operations¶
It should be noted that many programming languages provide a priority queue, which is an abstract data structure defined as a queue with priority sorting.
In fact, heaps are typically used to implement priority queues, with max heaps corresponding to priority queues where elements are dequeued in descending order. From a usage perspective, we can regard "priority queue" and "heap" as equivalent data structures. Therefore, this book does not make a special distinction between the two and uniformly refers to them as "heap."
Common heap operations are shown in Table 8-1, and method names need to be determined based on the programming language.
Table 8-1 Efficiency of Heap Operations
| Method name | Description | Time complexity |
|---|---|---|
push() |
Insert an element into the heap | \(O(\log n)\) |
pop() |
Remove the heap top element | \(O(\log n)\) |
peek() |
Access the heap top element (max/min value for max/min heap) | \(O(1)\) |
size() |
Get the number of elements in the heap | \(O(1)\) |
isEmpty() |
Check if the heap is empty | \(O(1)\) |
In practical applications, we can directly use the heap class (or priority queue class) provided by programming languages.
Similar to "ascending order" and "descending order" in sorting algorithms, we can implement conversion between "min heap" and "max heap" by setting a flag or modifying the Comparator. The code is as follows:
heap.py
# Initialize a min heap
min_heap, flag = [], 1
# Initialize a max heap
max_heap, flag = [], -1
# Python's heapq module implements a min heap by default
# Consider negating elements before pushing them to the heap, which inverts the size relationship and thus implements a max heap
# In this example, flag = 1 corresponds to a min heap, flag = -1 corresponds to a max heap
# Push elements into the heap
heapq.heappush(max_heap, flag * 1)
heapq.heappush(max_heap, flag * 3)
heapq.heappush(max_heap, flag * 2)
heapq.heappush(max_heap, flag * 5)
heapq.heappush(max_heap, flag * 4)
# Get the heap top element
peek: int = flag * max_heap[0] # 5
# Remove the heap top element
# The removed elements will form a descending sequence
val = flag * heapq.heappop(max_heap) # 5
val = flag * heapq.heappop(max_heap) # 4
val = flag * heapq.heappop(max_heap) # 3
val = flag * heapq.heappop(max_heap) # 2
val = flag * heapq.heappop(max_heap) # 1
# Get the heap size
size: int = len(max_heap)
# Check if the heap is empty
is_empty: bool = not max_heap
# Build a heap from an input list
min_heap: list[int] = [1, 3, 2, 5, 4]
heapq.heapify(min_heap)
heap.cpp
/* Initialize a heap */
// Initialize a min heap
priority_queue<int, vector<int>, greater<int>> minHeap;
// Initialize a max heap
priority_queue<int, vector<int>, less<int>> maxHeap;
/* Push elements into the heap */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);
/* Get the heap top element */
int peek = maxHeap.top(); // 5
/* Remove the heap top element */
// The removed elements will form a descending sequence
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1
/* Get the heap size */
int size = maxHeap.size();
/* Check if the heap is empty */
bool isEmpty = maxHeap.empty();
/* Build a heap from an input list */
vector<int> input{1, 3, 2, 5, 4};
priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end());
heap.java
/* Initialize a heap */
// Initialize a min heap
Queue<Integer> minHeap = new PriorityQueue<>();
// Initialize a max heap (use lambda expression to modify Comparator)
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
/* Push elements into the heap */
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(5);
maxHeap.offer(4);
/* Get the heap top element */
int peek = maxHeap.peek(); // 5
/* Remove the heap top element */
// The removed elements will form a descending sequence
peek = maxHeap.poll(); // 5
peek = maxHeap.poll(); // 4
peek = maxHeap.poll(); // 3
peek = maxHeap.poll(); // 2
peek = maxHeap.poll(); // 1
/* Get the heap size */
int size = maxHeap.size();
/* Check if the heap is empty */
boolean isEmpty = maxHeap.isEmpty();
/* Build a heap from an input list */
minHeap = new PriorityQueue<>(Arrays.asList(1, 3, 2, 5, 4));
heap.cs
/* Initialize a heap */
// Initialize a min heap
PriorityQueue<int, int> minHeap = new();
// Initialize a max heap (use lambda expression to modify Comparer)
PriorityQueue<int, int> maxHeap = new(Comparer<int>.Create((x, y) => y.CompareTo(x)));
/* Push elements into the heap */
maxHeap.Enqueue(1, 1);
maxHeap.Enqueue(3, 3);
maxHeap.Enqueue(2, 2);
maxHeap.Enqueue(5, 5);
maxHeap.Enqueue(4, 4);
/* Get the heap top element */
int peek = maxHeap.Peek();//5
/* Remove the heap top element */
// The removed elements will form a descending sequence
peek = maxHeap.Dequeue(); // 5
peek = maxHeap.Dequeue(); // 4
peek = maxHeap.Dequeue(); // 3
peek = maxHeap.Dequeue(); // 2
peek = maxHeap.Dequeue(); // 1
/* Get the heap size */
int size = maxHeap.Count;
/* Check if the heap is empty */
bool isEmpty = maxHeap.Count == 0;
/* Build a heap from an input list */
minHeap = new PriorityQueue<int, int>([(1, 1), (3, 3), (2, 2), (5, 5), (4, 4)]);
heap.go
// In Go, we can construct a max heap of integers by implementing heap.Interface
// Implementing heap.Interface also requires implementing sort.Interface
type intHeap []any
// Push implements the heap.Interface method for pushing an element into the heap
func (h *intHeap) Push(x any) {
// Push and Pop use pointer receiver as parameters
// because they not only adjust the slice contents but also modify the slice length
*h = append(*h, x.(int))
}
// Pop implements the heap.Interface method for popping the heap top element
func (h *intHeap) Pop() any {
// The element to be removed is stored at the end
last := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return last
}
// Len is a sort.Interface method
func (h *intHeap) Len() int {
return len(*h)
}
// Less is a sort.Interface method
func (h *intHeap) Less(i, j int) bool {
// To implement a min heap, change this to a less-than sign
return (*h)[i].(int) > (*h)[j].(int)
}
// Swap is a sort.Interface method
func (h *intHeap) Swap(i, j int) {
(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}
// Top gets the heap top element
func (h *intHeap) Top() any {
return (*h)[0]
}
/* Driver Code */
func TestHeap(t *testing.T) {
/* Initialize a heap */
// Initialize a max heap
maxHeap := &intHeap{}
heap.Init(maxHeap)
/* Push elements into the heap */
// Call heap.Interface methods to add elements
heap.Push(maxHeap, 1)
heap.Push(maxHeap, 3)
heap.Push(maxHeap, 2)
heap.Push(maxHeap, 4)
heap.Push(maxHeap, 5)
/* Get the heap top element */
top := maxHeap.Top()
fmt.Printf("Heap top element is %d\n", top)
/* Remove the heap top element */
// Call heap.Interface methods to remove elements
heap.Pop(maxHeap) // 5
heap.Pop(maxHeap) // 4
heap.Pop(maxHeap) // 3
heap.Pop(maxHeap) // 2
heap.Pop(maxHeap) // 1
/* Get the heap size */
size := len(*maxHeap)
fmt.Printf("Number of heap elements is %d\n", size)
/* Check if the heap is empty */
isEmpty := len(*maxHeap) == 0
fmt.Printf("Is the heap empty? %t\n", isEmpty)
}
heap.swift
/* Initialize a heap */
// Swift's Heap type supports both max heaps and min heaps, and requires importing swift-collections
var heap = Heap<Int>()
/* Push elements into the heap */
heap.insert(1)
heap.insert(3)
heap.insert(2)
heap.insert(5)
heap.insert(4)
/* Get the heap top element */
var peek = heap.max()!
/* Remove the heap top element */
peek = heap.removeMax() // 5
peek = heap.removeMax() // 4
peek = heap.removeMax() // 3
peek = heap.removeMax() // 2
peek = heap.removeMax() // 1
/* Get the heap size */
let size = heap.count
/* Check if the heap is empty */
let isEmpty = heap.isEmpty
/* Build a heap from an input list */
let heap2 = Heap([1, 3, 2, 5, 4])
heap.rs
use std::collections::BinaryHeap;
use std::cmp::Reverse;
/* Initialize a heap */
// Initialize a min heap
let mut min_heap = BinaryHeap::<Reverse<i32>>::new();
// Initialize a max heap
let mut max_heap = BinaryHeap::new();
/* Push elements into the heap */
max_heap.push(1);
max_heap.push(3);
max_heap.push(2);
max_heap.push(5);
max_heap.push(4);
/* Get the heap top element */
let peek = max_heap.peek().unwrap(); // 5
/* Remove the heap top element */
// The removed elements will form a descending sequence
let peek = max_heap.pop().unwrap(); // 5
let peek = max_heap.pop().unwrap(); // 4
let peek = max_heap.pop().unwrap(); // 3
let peek = max_heap.pop().unwrap(); // 2
let peek = max_heap.pop().unwrap(); // 1
/* Get the heap size */
let size = max_heap.len();
/* Check if the heap is empty */
let is_empty = max_heap.is_empty();
/* Build a heap from an input list */
let min_heap = BinaryHeap::from(vec![Reverse(1), Reverse(3), Reverse(2), Reverse(5), Reverse(4)]);
heap.kt
/* Initialize a heap */
// Initialize a min heap
var minHeap = PriorityQueue<Int>()
// Initialize a max heap (use lambda expression to modify Comparator)
val maxHeap = PriorityQueue { a: Int, b: Int -> b - a }
/* Push elements into the heap */
maxHeap.offer(1)
maxHeap.offer(3)
maxHeap.offer(2)
maxHeap.offer(5)
maxHeap.offer(4)
/* Get the heap top element */
var peek = maxHeap.peek() // 5
/* Remove the heap top element */
// The removed elements will form a descending sequence
peek = maxHeap.poll() // 5
peek = maxHeap.poll() // 4
peek = maxHeap.poll() // 3
peek = maxHeap.poll() // 2
peek = maxHeap.poll() // 1
/* Get the heap size */
val size = maxHeap.size
/* Check if the heap is empty */
val isEmpty = maxHeap.isEmpty()
/* Build a heap from an input list */
minHeap = PriorityQueue(mutableListOf(1, 3, 2, 5, 4))
Code Visualization
8.1.2 Implementation of the Heap¶
The following implementation is of a max heap. To convert it to a min heap, simply invert all size logic comparisons (for example, replace \(\geq\) with \(\leq\)). Interested readers are encouraged to implement this on their own.
1. Heap Storage and Representation¶
As mentioned in the "Binary Tree" chapter, complete binary trees are well-suited for array representation. Since heaps are a type of complete binary tree, we will use arrays to store heaps.
When representing a binary tree with an array, elements represent node values, and indexes represent node positions in the binary tree. Node pointers are implemented through index mapping formulas.
As shown in Figure 8-2, given an index \(i\), the index of its left child is \(2i + 1\), the index of its right child is \(2i + 2\), and the index of its parent is \((i - 1) / 2\) (floor division). When an index is out of bounds, it indicates a null node or that the node does not exist.
Figure 8-2 Representation and storage of heaps
We can encapsulate the index mapping formula into functions for convenient subsequent use:
2. Accessing the Heap Top Element¶
The heap top element is the root node of the binary tree, which is also the first element of the list:
3. Inserting an Element Into the Heap¶
Given an element val, we first add it to the bottom of the heap. After addition, since val may be larger than other elements in the heap, the heap's property may be violated. Therefore, it's necessary to repair the path from the inserted node to the root node. This operation is called heapify.
Starting from the inserted node, perform heapify from bottom to top. As shown in Figure 8-3, we compare the inserted node with its parent node, and if the inserted node is larger, swap them. Then continue this operation, repairing nodes in the heap from bottom to top until we pass the root node or encounter a node that does not need swapping.
Figure 8-3 Steps of inserting an element into the heap
Given a total of \(n\) nodes, the tree height is \(O(\log n)\). Thus, the number of loop iterations in the heapify operation is at most \(O(\log n)\), making the time complexity of the element insertion operation \(O(\log n)\). The code is as follows:
my_heap.py
def push(self, val: int):
"""Element enters heap"""
# Add node
self.max_heap.append(val)
# Heapify from bottom to top
self.sift_up(self.size() - 1)
def sift_up(self, i: int):
"""Starting from node i, heapify from bottom to top"""
while True:
# Get parent node of node i
p = self.parent(i)
# When "crossing root node" or "node needs no repair", end heapify
if p < 0 or self.max_heap[i] <= self.max_heap[p]:
break
# Swap two nodes
self.swap(i, p)
# Loop upward heapify
i = p
my_heap.cpp
/* Element enters heap */
void push(int val) {
// Add node
maxHeap.push_back(val);
// Heapify from bottom to top
siftUp(size() - 1);
}
/* Starting from node i, heapify from bottom to top */
void siftUp(int i) {
while (true) {
// Get parent node of node i
int p = parent(i);
// When "crossing root node" or "node needs no repair", end heapify
if (p < 0 || maxHeap[i] <= maxHeap[p])
break;
// Swap two nodes
swap(maxHeap[i], maxHeap[p]);
// Loop upward heapify
i = p;
}
}
my_heap.java
/* Element enters heap */
void push(int val) {
// Add node
maxHeap.add(val);
// Heapify from bottom to top
siftUp(size() - 1);
}
/* Starting from node i, heapify from bottom to top */
void siftUp(int i) {
while (true) {
// Get parent node of node i
int p = parent(i);
// When "crossing root node" or "node needs no repair", end heapify
if (p < 0 || maxHeap.get(i) <= maxHeap.get(p))
break;
// Swap two nodes
swap(i, p);
// Loop upward heapify
i = p;
}
}
my_heap.cs
/* Element enters heap */
void Push(int val) {
// Add node
maxHeap.Add(val);
// Heapify from bottom to top
SiftUp(Size() - 1);
}
/* Starting from node i, heapify from bottom to top */
void SiftUp(int i) {
while (true) {
// Get parent node of node i
int p = Parent(i);
// If 'past root node' or 'node needs no repair', end heapify
if (p < 0 || maxHeap[i] <= maxHeap[p])
break;
// Swap two nodes
Swap(i, p);
// Loop upward heapify
i = p;
}
}
my_heap.go
/* Element enters heap */
func (h *maxHeap) push(val any) {
// Add node
h.data = append(h.data, val)
// Heapify from bottom to top
h.siftUp(len(h.data) - 1)
}
/* Starting from node i, heapify from bottom to top */
func (h *maxHeap) siftUp(i int) {
for true {
// Get parent node of node i
p := h.parent(i)
// When "crossing root node" or "node needs no repair", end heapify
if p < 0 || h.data[i].(int) <= h.data[p].(int) {
break
}
// Swap two nodes
h.swap(i, p)
// Loop upward heapify
i = p
}
}
my_heap.swift
/* Element enters heap */
func push(val: Int) {
// Add node
maxHeap.append(val)
// Heapify from bottom to top
siftUp(i: size() - 1)
}
/* Starting from node i, heapify from bottom to top */
func siftUp(i: Int) {
var i = i
while true {
// Get parent node of node i
let p = parent(i: i)
// When "crossing root node" or "node needs no repair", end heapify
if p < 0 || maxHeap[i] <= maxHeap[p] {
break
}
// Swap two nodes
swap(i: i, j: p)
// Loop upward heapify
i = p
}
}
my_heap.js
/* Element enters heap */
push(val) {
// Add node
this.#maxHeap.push(val);
// Heapify from bottom to top
this.#siftUp(this.size() - 1);
}
/* Starting from node i, heapify from bottom to top */
#siftUp(i) {
while (true) {
// Get parent node of node i
const p = this.#parent(i);
// When "crossing root node" or "node needs no repair", end heapify
if (p < 0 || this.#maxHeap[i] <= this.#maxHeap[p]) break;
// Swap two nodes
this.#swap(i, p);
// Loop upward heapify
i = p;
}
}
my_heap.ts
/* Element enters heap */
push(val: number): void {
// Add node
this.maxHeap.push(val);
// Heapify from bottom to top
this.siftUp(this.size() - 1);
}
/* Starting from node i, heapify from bottom to top */
siftUp(i: number): void {
while (true) {
// Get parent node of node i
const p = this.parent(i);
// When "crossing root node" or "node needs no repair", end heapify
if (p < 0 || this.maxHeap[i] <= this.maxHeap[p]) break;
// Swap two nodes
this.swap(i, p);
// Loop upward heapify
i = p;
}
}
my_heap.dart
/* Element enters heap */
void push(int val) {
// Add node
_maxHeap.add(val);
// Heapify from bottom to top
siftUp(size() - 1);
}
/* Starting from node i, heapify from bottom to top */
void siftUp(int i) {
while (true) {
// Get parent node of node i
int p = _parent(i);
// When "crossing root node" or "node needs no repair", end heapify
if (p < 0 || _maxHeap[i] <= _maxHeap[p]) {
break;
}
// Swap two nodes
_swap(i, p);
// Loop upward heapify
i = p;
}
}
my_heap.rs
/* Element enters heap */
fn push(&mut self, val: i32) {
// Add node
self.max_heap.push(val);
// Heapify from bottom to top
self.sift_up(self.size() - 1);
}
/* Starting from node i, heapify from bottom to top */
fn sift_up(&mut self, mut i: usize) {
loop {
// Node i is already the heap root, end heapification
if i == 0 {
break;
}
// Get parent node of node i
let p = Self::parent(i);
// When "node needs no repair", end heapification
if self.max_heap[i] <= self.max_heap[p] {
break;
}
// Swap two nodes
self.swap(i, p);
// Loop upward heapify
i = p;
}
}
my_heap.c
/* Element enters heap */
void push(MaxHeap *maxHeap, int val) {
// By default, should not add this many nodes
if (maxHeap->size == MAX_SIZE) {
printf("heap is full!");
return;
}
// Add node
maxHeap->data[maxHeap->size] = val;
maxHeap->size++;
// Heapify from bottom to top
siftUp(maxHeap, maxHeap->size - 1);
}
/* Starting from node i, heapify from bottom to top */
void siftUp(MaxHeap *maxHeap, int i) {
while (true) {
// Get parent node of node i
int p = parent(maxHeap, i);
// When "crossing root node" or "node needs no repair", end heapify
if (p < 0 || maxHeap->data[i] <= maxHeap->data[p]) {
break;
}
// Swap two nodes
swap(maxHeap, i, p);
// Loop upward heapify
i = p;
}
}
my_heap.kt
/* Element enters heap */
fun push(_val: Int) {
// Add node
maxHeap.add(_val)
// Heapify from bottom to top
siftUp(size() - 1)
}
/* Starting from node i, heapify from bottom to top */
fun siftUp(it: Int) {
// Kotlin function parameters are immutable, so create temporary variable
var i = it
while (true) {
// Get parent node of node i
val p = parent(i)
// When "crossing root node" or "node needs no repair", end heapify
if (p < 0 || maxHeap[i] <= maxHeap[p]) break
// Swap two nodes
swap(i, p)
// Loop upward heapify
i = p
}
}
my_heap.rb
### Push element to heap ###
def push(val)
# Add node
@max_heap << val
# Heapify from bottom to top
sift_up(size - 1)
end
### Heapify from node i, bottom to top ###
def sift_up(i)
loop do
# Get parent node of node i
p = parent(i)
# When "crossing root node" or "node needs no repair", end heapify
break if p < 0 || @max_heap[i] <= @max_heap[p]
# Swap two nodes
swap(i, p)
# Loop upward heapify
i = p
end
end
4. Removing the Heap Top Element¶
The heap top element is the root node of the binary tree, which is the first element of the list. If we directly remove the first element from the list, all node indexes in the binary tree would change, making subsequent repair with heapify difficult. To minimize changes in element indexes, we use the following steps.
- Swap the heap top element with the heap bottom element (swap the root node with the rightmost leaf node).
- After swapping, remove the heap bottom from the list (note that since we've swapped, we're actually removing the original heap top element).
- Starting from the root node, perform heapify from top to bottom.
As shown in Figure 8-4, the direction of "top-to-bottom heapify" is opposite to "bottom-to-top heapify". We compare the root node's value with its two children and swap it with the largest child. Then loop this operation until we pass a leaf node or encounter a node that doesn't need swapping.
Figure 8-4 Steps of removing the heap top element
Similar to the element insertion operation, the time complexity of the heap top element removal operation is also \(O(\log n)\). The code is as follows:
my_heap.py
def pop(self) -> int:
"""Element exits heap"""
# Handle empty case
if self.is_empty():
raise IndexError("Heap is empty")
# Swap root node with rightmost leaf node (swap first element with last element)
self.swap(0, self.size() - 1)
# Delete node
val = self.max_heap.pop()
# Heapify from top to bottom
self.sift_down(0)
# Return top element
return val
def sift_down(self, i: int):
"""Starting from node i, heapify from top to bottom"""
while True:
# Find node with largest value among i, l, r, denoted as ma
l, r, ma = self.left(i), self.right(i), i
if l < self.size() and self.max_heap[l] > self.max_heap[ma]:
ma = l
if r < self.size() and self.max_heap[r] > self.max_heap[ma]:
ma = r
# If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
if ma == i:
break
# Swap two nodes
self.swap(i, ma)
# Loop downward heapify
i = ma
my_heap.cpp
/* Element exits heap */
void pop() {
// Handle empty case
if (isEmpty()) {
throw out_of_range("Heap is empty");
}
// Delete node
swap(maxHeap[0], maxHeap[size() - 1]);
// Remove node
maxHeap.pop_back();
// Return top element
siftDown(0);
}
/* Starting from node i, heapify from top to bottom */
void siftDown(int i) {
while (true) {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
int l = left(i), r = right(i), ma = i;
if (l < size() && maxHeap[l] > maxHeap[ma])
ma = l;
if (r < size() && maxHeap[r] > maxHeap[ma])
ma = r;
// Swap two nodes
if (ma == i)
break;
swap(maxHeap[i], maxHeap[ma]);
// Loop downwards heapification
i = ma;
}
}
my_heap.java
/* Element exits heap */
int pop() {
// Handle empty case
if (isEmpty())
throw new IndexOutOfBoundsException();
// Delete node
swap(0, size() - 1);
// Remove node
int val = maxHeap.remove(size() - 1);
// Return top element
siftDown(0);
// Return heap top element
return val;
}
/* Starting from node i, heapify from top to bottom */
void siftDown(int i) {
while (true) {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
int l = left(i), r = right(i), ma = i;
if (l < size() && maxHeap.get(l) > maxHeap.get(ma))
ma = l;
if (r < size() && maxHeap.get(r) > maxHeap.get(ma))
ma = r;
// Swap two nodes
if (ma == i)
break;
// Swap two nodes
swap(i, ma);
// Loop downwards heapification
i = ma;
}
}
my_heap.cs
/* Element exits heap */
int Pop() {
// Handle empty case
if (IsEmpty())
throw new IndexOutOfRangeException();
// Delete node
Swap(0, Size() - 1);
// Remove node
int val = maxHeap.Last();
maxHeap.RemoveAt(Size() - 1);
// Return top element
SiftDown(0);
// Return heap top element
return val;
}
/* Starting from node i, heapify from top to bottom */
void SiftDown(int i) {
while (true) {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
int l = Left(i), r = Right(i), ma = i;
if (l < Size() && maxHeap[l] > maxHeap[ma])
ma = l;
if (r < Size() && maxHeap[r] > maxHeap[ma])
ma = r;
// If 'node i is largest' or 'past leaf node', end heapify
if (ma == i) break;
// Swap two nodes
Swap(i, ma);
// Loop downwards heapification
i = ma;
}
}
my_heap.go
/* Element exits heap */
func (h *maxHeap) pop() any {
// Handle empty case
if h.isEmpty() {
fmt.Println("error")
return nil
}
// Delete node
h.swap(0, h.size()-1)
// Remove node
val := h.data[len(h.data)-1]
h.data = h.data[:len(h.data)-1]
// Return top element
h.siftDown(0)
// Return heap top element
return val
}
/* Starting from node i, heapify from top to bottom */
func (h *maxHeap) siftDown(i int) {
for true {
// Find node with maximum value among nodes i, l, r, denoted as max
l, r, max := h.left(i), h.right(i), i
if l < h.size() && h.data[l].(int) > h.data[max].(int) {
max = l
}
if r < h.size() && h.data[r].(int) > h.data[max].(int) {
max = r
}
// Swap two nodes
if max == i {
break
}
// Swap two nodes
h.swap(i, max)
// Loop downwards heapification
i = max
}
}
my_heap.swift
/* Element exits heap */
func pop() -> Int {
// Handle empty case
if isEmpty() {
fatalError("Heap is empty")
}
// Delete node
swap(i: 0, j: size() - 1)
// Remove node
let val = maxHeap.remove(at: size() - 1)
// Return top element
siftDown(i: 0)
// Return heap top element
return val
}
/* Starting from node i, heapify from top to bottom */
func siftDown(i: Int) {
var i = i
while true {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
let l = left(i: i)
let r = right(i: i)
var ma = i
if l < size(), maxHeap[l] > maxHeap[ma] {
ma = l
}
if r < size(), maxHeap[r] > maxHeap[ma] {
ma = r
}
// Swap two nodes
if ma == i {
break
}
// Swap two nodes
swap(i: i, j: ma)
// Loop downwards heapification
i = ma
}
}
my_heap.js
/* Element exits heap */
pop() {
// Handle empty case
if (this.isEmpty()) throw new Error('Heap is empty');
// Delete node
this.#swap(0, this.size() - 1);
// Remove node
const val = this.#maxHeap.pop();
// Return top element
this.#siftDown(0);
// Return heap top element
return val;
}
/* Starting from node i, heapify from top to bottom */
#siftDown(i) {
while (true) {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
const l = this.#left(i),
r = this.#right(i);
let ma = i;
if (l < this.size() && this.#maxHeap[l] > this.#maxHeap[ma]) ma = l;
if (r < this.size() && this.#maxHeap[r] > this.#maxHeap[ma]) ma = r;
// Swap two nodes
if (ma === i) break;
// Swap two nodes
this.#swap(i, ma);
// Loop downwards heapification
i = ma;
}
}
my_heap.ts
/* Element exits heap */
pop(): number {
// Handle empty case
if (this.isEmpty()) throw new RangeError('Heap is empty.');
// Delete node
this.swap(0, this.size() - 1);
// Remove node
const val = this.maxHeap.pop();
// Return top element
this.siftDown(0);
// Return heap top element
return val;
}
/* Starting from node i, heapify from top to bottom */
siftDown(i: number): void {
while (true) {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
const l = this.left(i),
r = this.right(i);
let ma = i;
if (l < this.size() && this.maxHeap[l] > this.maxHeap[ma]) ma = l;
if (r < this.size() && this.maxHeap[r] > this.maxHeap[ma]) ma = r;
// Swap two nodes
if (ma === i) break;
// Swap two nodes
this.swap(i, ma);
// Loop downwards heapification
i = ma;
}
}
my_heap.dart
/* Element exits heap */
int pop() {
// Handle empty case
if (isEmpty()) throw Exception('Heap is empty');
// Delete node
_swap(0, size() - 1);
// Remove node
int val = _maxHeap.removeLast();
// Return top element
siftDown(0);
// Return heap top element
return val;
}
/* Starting from node i, heapify from top to bottom */
void siftDown(int i) {
while (true) {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
int l = _left(i);
int r = _right(i);
int ma = i;
if (l < size() && _maxHeap[l] > _maxHeap[ma]) ma = l;
if (r < size() && _maxHeap[r] > _maxHeap[ma]) ma = r;
// Swap two nodes
if (ma == i) break;
// Swap two nodes
_swap(i, ma);
// Loop downwards heapification
i = ma;
}
}
my_heap.rs
/* Element exits heap */
fn pop(&mut self) -> i32 {
// Handle empty case
if self.is_empty() {
panic!("index out of bounds");
}
// Delete node
self.swap(0, self.size() - 1);
// Remove node
let val = self.max_heap.pop().unwrap();
// Return top element
self.sift_down(0);
// Return heap top element
val
}
/* Starting from node i, heapify from top to bottom */
fn sift_down(&mut self, mut i: usize) {
loop {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
let (l, r, mut ma) = (Self::left(i), Self::right(i), i);
if l < self.size() && self.max_heap[l] > self.max_heap[ma] {
ma = l;
}
if r < self.size() && self.max_heap[r] > self.max_heap[ma] {
ma = r;
}
// Swap two nodes
if ma == i {
break;
}
// Swap two nodes
self.swap(i, ma);
// Loop downwards heapification
i = ma;
}
}
my_heap.c
/* Element exits heap */
int pop(MaxHeap *maxHeap) {
// Handle empty case
if (isEmpty(maxHeap)) {
printf("heap is empty!");
return INT_MAX;
}
// Delete node
swap(maxHeap, 0, size(maxHeap) - 1);
// Remove node
int val = maxHeap->data[maxHeap->size - 1];
maxHeap->size--;
// Return top element
siftDown(maxHeap, 0);
// Return heap top element
return val;
}
/* Starting from node i, heapify from top to bottom */
void siftDown(MaxHeap *maxHeap, int i) {
while (true) {
// Find node with maximum value among nodes i, l, r, denoted as max
int l = left(maxHeap, i);
int r = right(maxHeap, i);
int max = i;
if (l < size(maxHeap) && maxHeap->data[l] > maxHeap->data[max]) {
max = l;
}
if (r < size(maxHeap) && maxHeap->data[r] > maxHeap->data[max]) {
max = r;
}
// Swap two nodes
if (max == i) {
break;
}
// Swap two nodes
swap(maxHeap, i, max);
// Loop downwards heapification
i = max;
}
}
my_heap.kt
/* Element exits heap */
fun pop(): Int {
// Handle empty case
if (isEmpty()) throw IndexOutOfBoundsException()
// Delete node
swap(0, size() - 1)
// Remove node
val _val = maxHeap.removeAt(size() - 1)
// Return top element
siftDown(0)
// Return heap top element
return _val
}
/* Starting from node i, heapify from top to bottom */
fun siftDown(it: Int) {
// Kotlin function parameters are immutable, so create temporary variable
var i = it
while (true) {
// If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
val l = left(i)
val r = right(i)
var ma = i
if (l < size() && maxHeap[l] > maxHeap[ma]) ma = l
if (r < size() && maxHeap[r] > maxHeap[ma]) ma = r
// Swap two nodes
if (ma == i) break
// Swap two nodes
swap(i, ma)
// Loop downwards heapification
i = ma
}
}
my_heap.rb
### Pop element from heap ###
def pop
# Handle empty case
raise IndexError, "Heap is empty" if is_empty?
# Delete node
swap(0, size - 1)
# Remove node
val = @max_heap.pop
# Return top element
sift_down(0)
# Return heap top element
val
end
### Heapify from node i, top to bottom ###
def sift_down(i)
loop do
# If node i is largest or indices l, r are out of bounds, no need to continue heapify, break
l, r, ma = left(i), right(i), i
ma = l if l < size && @max_heap[l] > @max_heap[ma]
ma = r if r < size && @max_heap[r] > @max_heap[ma]
# Swap two nodes
break if ma == i
# Swap two nodes
swap(i, ma)
# Loop downwards heapification
i = ma
end
end
8.1.3 Common Applications of Heaps¶
- Priority queue: Heaps are typically the preferred data structure for implementing priority queues, with both enqueue and dequeue operations having a time complexity of \(O(\log n)\), and the heap construction operation having \(O(n)\), all of which are highly efficient.
- Heap sort: Given a set of data, we can build a heap with them and then continuously perform element removal operations to obtain sorted data. However, we usually use a more elegant approach to implement heap sort, as detailed in the "Heap Sort" chapter.
- Getting the largest \(k\) elements: This is a classic algorithm problem and also a typical application, such as selecting the top 10 trending news for Weibo hot search, selecting the top 10 best-selling products, etc.