数据结构——堆

欢迎大家来到IT世界,在知识的湖畔探索吧!

数据结构教程：堆

一、定义与特性

堆是一种特殊的树形数据结构，通常是一个完全二叉树。堆有两种主要类型：最大堆和最小堆。

1. 最大堆：

在最大堆中，每个节点的值都大于或等于其子节点的值。根节点（顶部）始终是整个堆中的最大元素。

2. 最小堆：

在最小堆中，每个节点的值都小于或等于其子节点的值。根节点始终是最小元素。

二、基本操作与性质

1. 插入操作：

插入新元素后，可能需要向上调整（heapify-up），以保持堆的性质。

2. 删除操作：

删除堆顶元素（最大堆中为最大元素，最小堆中为最小元素）。删除后，将最后一个元素移动到堆顶，并向下调整（heapify-down）以恢复堆的性质。

3. 查找操作：

堆主要用于存储和检索最大或最小元素，但不直接支持高效的查找特定元素的操作。

4. 构建堆：

可以通过数组实现堆，从最后一个非叶子节点开始，依次对每个节点进行heapify-down操作来构建堆。

三、C++ 示例代码片段

#include <vector> class Heap { private: std::vector<int> heap; // 使用数组模拟堆 public: void insert(int value) { heap.push_back(value); siftUp(heap.size() - 1); // 插入新元素后的上浮操作 } int extractMax() { // 对于最大堆，提取最大元素 if (heap.empty()) return -1; int max = heap[0]; heap[0] = heap.back(); heap.pop_back(); siftDown(0); // 提取后下滤操作 return max; } private: // 上浮操作（针对最大堆） void siftUp(int i) { while (i > 0 && heap[parent(i)] < heap[i]) { swap(heap[parent(i)], heap[i]); i = parent(i); } } // 下滤操作（针对最大堆） void siftDown(int i) { while (true) { int left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left < heap.size() && heap[left] > heap[largest]) largest = left; if (right < heap.size() && heap[right] > heap[largest]) largest = right; if (largest != i) { swap(heap[i], heap[largest]); i = largest; } else { break; } } } // 计算父节点索引 static int parent(int i) { return (i - 1) / 2; } };

欢迎大家来到IT世界,在知识的湖畔探索吧!

总结：

堆作为高效的数据结构，在许多算法和实际应用中有重要地位，例如优先队列、堆排序等。它利用完全二叉树的特性实现了在O(log n)时间复杂度内插入、删除最大/最小元素的能力。通过维护堆的性质，可以确保即使在动态变化的数据集合中也能快速访问到当前的最大或最小元素。