大根堆和小根堆的介绍

堆(Heap)的基本概念

堆是一种完全二叉树(Complete Binary Tree),其性质使得堆可以高效地支持以下操作:

  • 插入(Insert):将一个新元素加入到堆中。
  • 删除最大/最小元素(Delete Max/Min):移除并返回堆中的最大(大根堆)或最小(小根堆)元素。
  • 获取最大/最小元素(Get Max/Min):返回堆中的最大(大根堆)或最小(小根堆)元素。

大根堆(Max-Heap)

特性

  • 每个节点的值都大于或等于其子节点的值。
  • 根节点是堆中最大的元素。

插入操作

  1. 将新元素插入到树的最底层的最后位置(保持完全二叉树的性质)。
  2. 进行“上浮”操作,将新元素逐步与其父节点交换,直到堆的性质恢复或到达根节点为止。

删除最大元素

  1. 移除根节点。
  2. 将最后一个元素移动到根位置。
  3. 进行“下沉”操作,将根节点逐步与其较大的子节点交换,直到堆的性质恢复或到达叶子节点为止。

小根堆(Min-Heap)

特性

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

插入操作

  1. 将新元素插入到树的最底层的最后位置(保持完全二叉树的性质)。
  2. 进行“上浮”操作,将新元素逐步与其父节点交换,直到堆的性质恢复或到达根节点为止。

删除最小元素

  1. 移除根节点。
  2. 将最后一个元素移动到根位置。
  3. 进行“下沉”操作,将根节点逐步与其较小的子节点交换,直到堆的性质恢复或到达叶子节点为止。

C++ 示例代码

以下是详细的 C++ 示例代码,展示如何实现大根堆和小根堆:

#include <iostream>
//在c++中,使用优先队列需要包含queue这个头文件
#include <queue>
#include <vector>

// 大根堆(默认行为)
void maxHeapExample() {
    // 创建一个大根堆
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);
    maxHeap.push(15);

    std::cout << "Max-Heap (大根堆): ";
    // 输出并删除堆顶元素
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " "; // 获取堆顶元素
        maxHeap.pop(); // 删除堆顶元素
    }
    std::cout << std::endl;
}

// 小根堆
void minHeapExample() {
    // 自定义比较函数,逆序(大根堆),实现小根堆
    auto cmp = [](int left, int right) { return left > right; };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> minHeap(cmp);

    // 插入元素
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);
    minHeap.push(15);

    std::cout << "Min-Heap (小根堆): ";
    // 输出并删除堆顶元素
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 获取堆顶元素
        minHeap.pop(); // 删除堆顶元素
    }
    std::cout << std::endl;
}

int main() {
    maxHeapExample();
    minHeapExample();

    return 0;
}

代码解释

  1. 大根堆(Max-Heap)
    • std::priority_queue<int> 默认是大根堆。priority_queue 是 STL 提供的容器适配器,基于堆实现。
    • 插入元素使用 push(),获取堆顶元素使用 top(),删除堆顶元素使用 pop()
  2. 小根堆(Min-Heap)
    • 通过自定义比较函数来实现小根堆。std::priority_queue 的构造函数允许传递自定义的比较函数。
    • auto cmp = [](int left, int right) { return left > right; }; 是一个 lambda 表达式,用于将小根堆的比较函数定义为 left > right
    • 构造 priority_queue 时,传递 cmp 作为比较函数,这样就会形成小根堆。

小根堆的实现细节与第二种实现方式

在 C++ 的 priority_queue 中,如果你不显式地提供第二个模板参数(即底层容器类型),它会默认使用 std::vector 作为底层容器。这意味着,你可以只指定元素类型和比较函数(或者不指定比较函数,使用默认的比较方式),而不必显式地指定底层容器类型。

示例:

#include <iostream>
#include <queue>

struct Compare {
    bool operator()(int left, int right) {
        // 小根堆的比较规则:左边的值小于右边的值返回 true
        return left > right;
    }
};

void minHeapExample() {
    // 不显式指定底层容器类型,仍然会使用默认的 std::vector<int>
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(5);
    minHeap.push(15);

    std::cout << "Min-Heap (小根堆): ";

    // 输出并删除堆顶元素
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 获取堆顶元素
        minHeap.pop(); // 删除堆顶元素
    }
    std::cout << std::endl;
}

int main() {
    minHeapExample();

    return 0;
}

解释:

  • std::priority_queue<int, std::vector<int>, Compare> minHeap; 中,我们没有显式地提供第二个模板参数(底层容器类型),因此默认使用 std::vector<int>
  • 这样做的好处是简化了代码,使其更具可读性,并且仍然能够正常使用小根堆的功能。
  • 如果你想要使用除了 std::vector 以外的其他底层容器,你可以显式地指定第二个模板参数,例如 std::deque<int> 或者其他适合的容器类型。

因此,答案是:可以不显式提供第二个模板参数 std::vector<int>priority_queue 能够识别到并使用默认的 std::vector 作为底层容器类型。

比较规则的解释

在 C++ 的 priority_queue 中,如果我们想要实现一个小根堆(Min Heap),是使用 left > right 的比较规则。

比较规则解释:

  1. 小根堆(Min Heap)

    • 在小根堆中,父节点的值应该小于或等于每个子节点的值。
    • 因此,在 C++ 的 priority_queue 中,应该使用比较函数或者仿函数,确保 leftright 大,即 left > right
  2. 大根堆(Max Heap)

    • 在大根堆中,父节点的值应该大于或等于每个子节点的值。
    • 因此,比较函数应该返回 left < right

示例解释:

如果要实现一个小根堆,确保堆顶元素是最小的,比较函数应该是这样定义的:

struct MinHeapComparator {
    bool operator()(int left, int right) {
        return left > right;
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, MinHeapComparator> minHeap;

    minHeap.push(10);
    minHeap.push(2);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(13);

    while (!minHeap.empty()) {
        int t = minHeap.top();
        minHeap.pop();
        std::cout << t << " ";
    }

    return 0;
}

在这个示例中,MinHeapComparator 是一个仿函数,它实现了小根堆的比较规则 left > right,确保了堆顶的元素是最小的。

总结:

对于小根堆的实现,确实应该使用 left > right 的比较规则。这个比较规则确保了在堆中,父节点的值小于或等于每个子节点的值,从而满足小根堆的特性。

热门相关:额外旅程   带着仙门混北欧   我会一直喜欢你   战神无双   佣兵的战争