首页 书籍 深入浅出程序设计竞赛(进阶篇) 进阶数据结构

# 二叉堆

二叉堆是一种特殊的完全二叉树。它分为两种类型：最大堆和最小堆。

  • 最大堆：任何一个父节点的值都大于或等于它的子节点的值。
  • 最小堆：任何一个父节点的值都小于或等于它的子节点的值。

二叉堆通常通过数组来实现。对于数组中的任意一个元素，设其索引为 i ，则：

  • 它的父节点的索引为 (i - 1) / 2 （当 i 为 0 时，该节点为根节点，无父节点）。
  • 它的左子节点的索引为 2*i + 1 。
  • 它的右子节点的索引为 2*i + 2 。

# 操作

二叉堆主要支持以下操作：

  • 插入（Insert）：将新元素加到堆的末尾，然后上浮到正确位置。
  • 删除最大元 / 最小元（Delete Max/Delete Min）：移除根节点，将最后一个元素移到根节点位置，然后下沉到正确位置。
  • 构建堆（Build Heap）：将无序数组转换成一个堆，通常使用自底向上的方法。

# 代码

下面是一个最小堆的 C++ 实现示例：

#include <iostream>
#include <vector>
using namespace std;
class MinHeap {
private:
    vector<int> heap; // 用 vector 存储堆元素
    // 返回父节点的索引
    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 siftUp(int i) {
        while (i != 0 && heap[parent(i)] > heap[i]) {
            swap(heap[parent(i)], heap[i]);
            i = parent(i);
        }
    }
    // 下沉调整
    void siftDown(int i) {
        int maxIndex = i;
        int l = leftChild(i);
        if (l < heap.size() && heap[l] < heap[maxIndex]) {
            maxIndex = l;
        }
        int r = rightChild(i);
        if (r < heap.size() && heap[r] < heap[maxIndex]) {
            maxIndex = r;
        }
        if (i != maxIndex) {
            swap(heap[i], heap[maxIndex]);
            siftDown(maxIndex);
        }
    }
public:
    // 插入新元素
    void insert(int p) {
        heap.push_back(p);
        siftUp(heap.size() - 1);
    }
    // 获取堆顶元素（最小元）
    int getMin() {
        return heap[0];
    }
    // 删除堆顶元素
    void removeMin() {
        heap[0] = heap.back();
        heap.pop_back();
        siftDown(0);
    }
    // 构建堆
    void buildHeap(const vector<int>& sourceArray) {
        heap = sourceArray;
        for (int i = parent(heap.size() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }
};
int main() {
    MinHeap minHeap;
    vector<int> array = {5, 3, 8, 4, 2, 9, 7, 1, 6};
    minHeap.buildHeap(array);
    cout << "Min element: " << minHeap.getMin() << endl; // 应输出 1
    minHeap.insert(0);
    cout << "New min element after inserting 0: " << minHeap.getMin() << endl; // 应输出 0
    minHeap.removeMin();
    cout << "Min element after removing min: " << minHeap.getMin() << endl; // 应输出 1
    return 0;
}
这段代码演示了最小堆的基本操作：构建堆、插入新元素、获取最小元素、删除最小元素。通过这些基础操作，可以实现更复杂的数据结构和算法，如优先队列、堆排序等。


# 优先队列


优先队列是一种特殊的队列，其中每个元素都有一个优先级。当访问元素时，具有最高优先级的元素最先被取出。优先队列可以使用不同的数据结构来实现，而二叉堆是实现优先队列的一种高效方式。


在二叉堆实现的优先队列中，根据是最大堆还是最小堆，可以实现最大优先队列或最小优先队列：


    

  • 最大优先队列：元素按优先级降序排列，最大元素（优先级最高）总是位于堆的顶部。
    • 

  • 最小优先队列：元素按优先级升序排列，最小元素（优先级最低）总是位于堆的顶部。
    • 



以下是使用最小堆实现最小优先队列的 C++ 示例代码：


#include <iostream>
#include <vector>
using namespace std;
class MinPriorityQueue {
private:
    vector<int> heap;
    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 siftUp(int i) {
        while (i != 0 && heap[parent(i)] > heap[i]) {
            swap(heap[parent(i)], heap[i]);
            i = parent(i);
        }
    }
    void siftDown(int i) {
        int minIndex = i;
        int l = leftChild(i);
        if (l < heap.size() && heap[l] < heap[minIndex]) {
            minIndex = l;
        }
        int r = rightChild(i);
        if (r < heap.size() && heap[r] < heap[minIndex]) {
            minIndex = r;
        }
        if (i != minIndex) {
            swap(heap[i], heap[minIndex]);
            siftDown(minIndex);
        }
    }
public:
    // 插入元素
    void insert(int p) {
        heap.push_back(p);
        siftUp(heap.size() - 1);
    }
    // 获取最小元素（优先级最高）
    int top() {
        if (!heap.empty())
            return heap[0];
        throw "Priority queue is empty";
    }
    // 删除最小元素
    void pop() {
        if (heap.empty()) {
            throw "Priority queue is empty";
        }
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            siftDown(0);
        }
    }
    // 检查优先队列是否为空
    bool isEmpty() const {
        return heap.empty();
    }
};
int main() {
    MinPriorityQueue pq;
    pq.insert(3);
    pq.insert(2);
    pq.insert(15);
    pq.insert(5);
    pq.insert(4);
    pq.insert(45);
    cout << "Element with highest priority: " << pq.top() << endl; // 应输出 2
    pq.pop();
    cout << "Next highest priority element: " << pq.top() << endl; // 应输出 3
    return 0;
}
这段代码展示了如何使用最小堆来实现一个最小优先队列，包括插入元素、获取最小元素（即优先级最高的元素）、删除最小元素以及检查优先队列是否为空的操作。通过调整 siftUp  和 siftDown  方法，同样可以实现基于最大堆的最大优先队列。


      

          
      

  


   


    

  
    
      
    
    更新于