二叉堆是一种特殊的完全二叉树,常用于实现优先队列。最小堆的每个节点的值都小于或等于其子节点的值,最大堆的每个节点的值都大于或等于其子节点的值。二叉堆支持高效的插入、删除最值和构建操作。
二叉堆是一种特殊的完全二叉树数据结构,它满足堆属性。完全二叉树是指除了最后一层外,其他层的节点都是满的,而最后一层的节点都靠左排列。二叉堆主要有两种类型:
二叉堆的这种特殊结构使得它可以高效地找到最大值或最小值,所以也常被用来实现优先队列。
向堆中添加一个新元素:
移除并返回堆顶元素(最大/最小值):
将一个元素向上移动到合适位置的过程:
将一个元素向下移动到合适位置的过程:
▼Java复制代码public class MinHeap { private int[] heap; private int size; private int capacity; // 构造函数 public MinHeap(int capacity) { this.capacity = capacity; this.size = 0; this.heap = new int[capacity]; } // 获取父节点索引 private int parent(int i) { return (i - 1) / 2; } // 获取左子节点索引 private int leftChild(int i) { return 2 * i + 1; } // 获取右子节点索引 private int rightChild(int i) { return 2 * i + 2; } // 交换两个节点 private void swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } // 插入元素 public void insert(int key) { if (size == capacity) { System.out.println("堆已满,无法插入"); return; } // 先将新元素插入到堆的末尾 heap[size] = key; int current = size; size++; // 上浮操作:将元素向上移动到合适位置 while (current > 0 && heap[current] < heap[parent(current)]) { swap(current, parent(current)); current = parent(current); } } // 获取最小元素(不删除) public int peek() { if (size <= 0) { System.out.println("堆为空"); return -1; } return heap[0]; } // 删除并返回最小元素 public int extractMin() { if (size <= 0) { System.out.println("堆为空"); return -1; } if (size == 1) { size--; return heap[0]; } // 存储根节点(最小值) int root = heap[0]; // 将最后一个元素放到根位置 heap[0] = heap[size - 1]; size--; // 下沉操作:将根元素向下移动到合适位置 heapifyDown(0); return root; } // 下沉操作 private void heapifyDown(int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); // 找出当前节点、左子节点和右子节点中的最小值 if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } // 如果最小值不是当前节点,则交换并继续下沉 if (smallest != i) { swap(i, smallest); heapifyDown(smallest); } } // 打印堆 public void printHeap() { for (int i = 0; i < size; i++) { System.out.print(heap[i] + " "); } System.out.println(); } public static void main(String[] args) { MinHeap minHeap = new MinHeap(10); minHeap.insert(5); minHeap.insert(3); minHeap.insert(8); minHeap.insert(1); minHeap.insert(10); System.out.println("构建的堆:"); minHeap.printHeap(); System.out.println("最小元素:" + minHeap.peek()); System.out.println("提取最小元素:" + minHeap.extractMin()); System.out.println("提取后的堆:"); minHeap.printHeap(); } }
▼Javascript复制代码class MinHeap { constructor(capacity) { this.capacity = capacity; this.size = 0; this.heap = new Array(capacity); } // 获取父节点索引 parent(i) { return Math.floor((i - 1) / 2); } // 获取左子节点索引 leftChild(i) { return 2 * i + 1; } // 获取右子节点索引 rightChild(i) { return 2 * i + 2; } // 交换两个节点 swap(i, j) { const temp = this.heap[i]; this.heap[i] = this.heap[j]; this.heap[j] = temp; } // 插入元素 insert(key) { if (this.size === this.capacity) { console.log("堆已满,无法插入"); return; } // 先将新元素插入到堆的末尾 this.heap[this.size] = key; let current = this.size; this.size++; // 上浮操作:将元素向上移动到合适位置 while (current > 0 && this.heap[current] < this.heap[this.parent(current)]) { this.swap(current, this.parent(current)); current = this.parent(current); } } // 获取最小元素(不删除) peek() { if (this.size <= 0) { console.log("堆为空"); return -1; } return this.heap[0]; } // 删除并返回最小元素 extractMin() { if (this.size <= 0) { console.log("堆为空"); return -1; } if (this.size === 1) { this.size--; return this.heap[0]; } // 存储根节点(最小值) const root = this.heap[0]; // 将最后一个元素放到根位置 this.heap[0] = this.heap[this.size - 1]; this.size--; // 下沉操作:将根元素向下移动到合适位置 this.heapifyDown(0); return root; } // 下沉操作 heapifyDown(i) { let smallest = i; const left = this.leftChild(i); const right = this.rightChild(i); // 找出当前节点、左子节点和右子节点中的最小值 if (left < this.size && this.heap[left] < this.heap[smallest]) { smallest = left; } if (right < this.size && this.heap[right] < this.heap[smallest]) { smallest = right; } // 如果最小值不是当前节点,则交换并继续下沉 if (smallest !== i) { this.swap(i, smallest); this.heapifyDown(smallest); } } // 打印堆 printHeap() { let output = ""; for (let i = 0; i < this.size; i++) { output += this.heap[i] + " "; } console.log(output); } } // 使用示例 function main() { const minHeap = new MinHeap(10); minHeap.insert(5); minHeap.insert(3); minHeap.insert(8); minHeap.insert(1); minHeap.insert(10); console.log("构建的堆:"); minHeap.printHeap(); console.log("最小元素:" + minHeap.peek()); console.log("提取最小元素:" + minHeap.extractMin()); console.log("提取后的堆:"); minHeap.printHeap(); } main();
▼Python复制代码class MinHeap: def __init__(self, capacity): self.capacity = capacity self.size = 0 self.heap = [0] * capacity # 获取父节点索引 def parent(self, i): return (i - 1) // 2 # 获取左子节点索引 def left_child(self, i): return 2 * i + 1 # 获取右子节点索引 def right_child(self, i): return 2 * i + 2 # 交换两个节点 def swap(self, i, j): self.heap[i], self.heap[j] = self.heap[j], self.heap[i] # 插入元素 def insert(self, key): if self.size == self.capacity: print("堆已满,无法插入") return # 先将新元素插入到堆的末尾 self.heap[self.size] = key current = self.size self.size += 1 # 上浮操作:将元素向上移动到合适位置 while current > 0 and self.heap[current] < self.heap[self.parent(current)]: self.swap(current, self.parent(current)) current = self.parent(current) # 获取最小元素(不删除) def peek(self): if self.size <= 0: print("堆为空") return -1 return self.heap[0] # 删除并返回最小元素 def extract_min(self): if self.size <= 0: print("堆为空") return -1 if self.size == 1: self.size -= 1 return self.heap[0] # 存储根节点(最小值) root = self.heap[0] # 将最后一个元素放到根位置 self.heap[0] = self.heap[self.size - 1] self.size -= 1 # 下沉操作:将根元素向下移动到合适位置 self.heapify_down(0) return root # 下沉操作 def heapify_down(self, i): smallest = i left = self.left_child(i) right = self.right_child(i) # 找出当前节点、左子节点和右子节点中的最小值 if left < self.size and self.heap[left] < self.heap[smallest]: smallest = left if right < self.size and self.heap[right] < self.heap[smallest]: smallest = right # 如果最小值不是当前节点,则交换并继续下沉 if smallest != i: self.swap(i, smallest) self.heapify_down(smallest) # 打印堆 def print_heap(self): print(" ".join(str(self.heap[i]) for i in range(self.size))) # 使用示例 def main(): min_heap = MinHeap(10) min_heap.insert(5) min_heap.insert(3) min_heap.insert(8) min_heap.insert(1) min_heap.insert(10) print("构建的堆:") min_heap.print_heap() print("最小元素:", min_heap.peek()) print("提取最小元素:", min_heap.extract_min()) print("提取后的堆:") min_heap.print_heap() if __name__ == "__main__": main()
▼Go复制代码package main import "fmt" // MinHeap 表示最小堆结构 type MinHeap struct { heap []int // 堆数组 size int // 当前堆大小 capacity int // 堆最大容量 } // NewMinHeap 创建一个指定容量的最小堆 func NewMinHeap(capacity int) *MinHeap { return &MinHeap{ heap: make([]int, capacity), size: 0, capacity: capacity, } } // 获取父节点索引 func (mh *MinHeap) parent(i int) int { return (i - 1) / 2 } // 获取左子节点索引 func (mh *MinHeap) leftChild(i int) int { return 2*i + 1 } // 获取右子节点索引 func (mh *MinHeap) rightChild(i int) int { return 2*i + 2 } // 交换两个节点的值 func (mh *MinHeap) swap(i, j int) { mh.heap[i], mh.heap[j] = mh.heap[j], mh.heap[i] } // Insert 向堆中插入新元素 func (mh *MinHeap) Insert(key int) { if mh.size == mh.capacity { fmt.Println("堆已满,无法插入") return } // 先将新元素插入到堆的末尾 mh.heap[mh.size] = key current := mh.size mh.size++ // 上浮操作:将元素向上移动到合适位置 for current > 0 && mh.heap[current] < mh.heap[mh.parent(current)] { mh.swap(current, mh.parent(current)) current = mh.parent(current) } } // Peek 获取堆顶元素(不删除) func (mh *MinHeap) Peek() int { if mh.size <= 0 { fmt.Println("堆为空") return -1 } return mh.heap[0] } // ExtractMin 删除并返回堆顶元素 func (mh *MinHeap) ExtractMin() int { if mh.size <= 0 { fmt.Println("堆为空") return -1 } if mh.size == 1 { mh.size-- return mh.heap[0] } // 存储根节点(最小值) root := mh.heap[0] // 将最后一个元素放到根位置 mh.heap[0] = mh.heap[mh.size-1] mh.size-- // 下沉操作:将根元素向下移动到合适位置 mh.heapifyDown(0) return root } // 下沉操作 func (mh *MinHeap) heapifyDown(i int) { smallest := i left := mh.leftChild(i) right := mh.rightChild(i) // 找出当前节点、左子节点和右子节点中的最小值 if left < mh.size && mh.heap[left] < mh.heap[smallest] { smallest = left } if right < mh.size && mh.heap[right] < mh.heap[smallest] { smallest = right } // 如果最小值不是当前节点,则交换并继续下沉 if smallest != i { mh.swap(i, smallest) mh.heapifyDown(smallest) } } // PrintHeap 打印堆的内容 func (mh *MinHeap) PrintHeap() { for i := 0; i < mh.size; i++ { fmt.Printf("%d ", mh.heap[i]) } fmt.Println() } func main() { minHeap := NewMinHeap(10) minHeap.Insert(5) minHeap.Insert(3) minHeap.Insert(8) minHeap.Insert(1) minHeap.Insert(10) fmt.Println("构建的堆:") minHeap.PrintHeap() fmt.Printf("最小元素:%d\n", minHeap.Peek()) fmt.Printf("提取最小元素:%d\n", minHeap.ExtractMin()) fmt.Println("提取后的堆:") minHeap.PrintHeap() }
▼C++复制代码#include <iostream> #include <vector> class MinHeap { private: std::vector<int> heap; int size; int capacity; // 获取父节点索引 int parent(int i) { return (i - 1) / 2; } // 获取左子节点索引 int leftChild(int i) { return 2 * i + 1; } // 获取右子节点索引 int rightChild(int i) { return 2 * i + 2; } // 交换两个节点 void swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } // 下沉操作 void heapifyDown(int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); // 找出当前节点、左子节点和右子节点中的最小值 if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } // 如果最小值不是当前节点,则交换并继续下沉 if (smallest != i) { swap(i, smallest); heapifyDown(smallest); } } public: // 构造函数 MinHeap(int cap) { capacity = cap; size = 0; heap.resize(capacity); } // 插入元素 void insert(int key) { if (size == capacity) { std::cout << "堆已满,无法插入" << std::endl; return; } // 先将新元素插入到堆的末尾 heap[size] = key int current = size size++ // 上浮操作:将元素向上移动到合适位置 while (current > 0 && heap[current] < heap[parent(current)]) { swap(current, parent(current)) current = parent(current) } } // 获取最小元素(不删除) int peek() { if (size <= 0) { std::cout << "堆为空" << std::endl; return -1; } return heap[0]; } // 删除并返回最小元素 int extractMin() { if (size <= 0) { std::cout << "堆为空" << std::endl; return -1; } if (size == 1) { size-- return heap[0] } // 存储根节点(最小值) int root = heap[0] // 将最后一个元素放到根位置 heap[0] = heap[size - 1] size-- // 下沉操作:将根元素向下移动到合适位置 heapifyDown(0) return root } // 打印堆 void printHeap() { for (int i = 0; i < size; i++) { std::cout << heap[i] << " "; } std::cout << std::endl; } }; int main() { MinHeap minHeap(10); minHeap.insert(5); minHeap.insert(3); minHeap.insert(8); minHeap.insert(1); minHeap.insert(10); std::cout << "构建的堆:" << std::endl; minHeap.printHeap(); std::cout << "最小元素:" << minHeap.peek() << std::endl; std::cout << "提取最小元素:" << minHeap.extractMin() << std::endl; std::cout << "提取后的堆:" << std::endl; minHeap.printHeap(); return 0; }
这两个实现都保持了二叉堆的基本操作和性能特性,但分别采用了Go和C++语言的特定语法和风格。
Go实现使用了Go语言的特性,如方法接收器和多返回值交换,而C++实现则利用了面向对象特性和STL容器(vector)来存储堆元素。两者都实现了相同的功能:创建堆、插入元素、获取最小元素、提取最小元素等操作。
二叉堆广泛应用于各种算法和系统中:
Java 提供了 PriorityQueue 类,它基于二叉堆实现:
▼Java复制代码import java.util.PriorityQueue; public class PriorityQueueExample { public static void main(String[] args) { // 默认是最小堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 添加元素 minHeap.add(5); minHeap.add(3); minHeap.add(8); minHeap.add(1); minHeap.add(10); System.out.println("优先队列内容:" + minHeap); System.out.println("最小元素:" + minHeap.peek()); System.out.println("提取最小元素:" + minHeap.poll()); System.out.println("提取后的优先队列:" + minHeap); // 创建最大堆(通过自定义比较器) PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); maxHeap.add(5); maxHeap.add(3); maxHeap.add(8); maxHeap.add(1); maxHeap.add(10); System.out.println("最大堆内容:" + maxHeap); System.out.println("最大元素:" + maxHeap.peek()); } }
除了基本的二叉堆,还有几种重要的堆变种:
测验答案
- 二叉堆是一种特殊的完全二叉树数据结构,它满足堆属性。主要有两种类型:最大堆(父节点值大于等于子节点值)和最小堆(父节点值小于等于子节点值)。
- 在数组表示的堆中,如果一个节点的索引是i,那么它的左子节点索引是2i+1,右子节点索引是2i+2。元素5的索引是1,所以它的左子节点是索引为3的元素6,右子节点是索引为4的元素9。
- 1)查找最大/最小元素:O(1) 2)插入新元素:O(log n) 3)删除堆顶元素:O(log n)
- 将无序数组转换为堆的时间复杂度是O(n),这比直观预期的O(n log n)要好。因为使用了自底向上的建堆方法,对大多数节点只需要很少的下沉操作。
- 二叉堆使用数组实现有几个优点:1) 不需要额外的指针开销,节省内存;2) 利用索引公式可以直接计算父子节点位置,无需存储额外引用;3) 数组的连续内存分配提供了更好的内存局部性,有利于缓存性能;4) 实现简单,易于理解和维护。