小顶堆和大顶堆详解

小蓝 • 2024-11-14 03:03 • 编程

一、小顶堆和大顶堆stl

STL中提供了小顶堆和大顶堆的实现，可以通过传入比较函数来指定为小顶堆和大顶堆。例如：

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    // 小顶堆
    priority_queue<int, vector<int>, greater<int>> pq1;
    pq1.push(3);
    pq1.push(1);
    pq1.push(2);
    while (!pq1.empty())
    {
        cout << pq1.top() << " ";
        pq1.pop();
    }
    // 输出结果为：1 2 3

    // 大顶堆
    priority_queue<int, vector<int>> pq2;
    pq2.push(3);
    pq2.push(1);
    pq2.push(2);
    while (!pq2.empty())
    {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    // 输出结果为：3 2 1

    return 0;
}

二、小顶堆和大顶堆区别

小顶堆是一种每个节点都小于等于其父节点的完全二叉树，最小的元素在根节点，而大顶堆是每个节点都大于等于其子节点的完全二叉树，最大的元素在根节点。在实现中，小顶堆和大顶堆都需要维护堆的性质，即父节点与其子节点之间的大小关系。

三、大顶堆小顶堆的定义

大顶堆是一种每个节点都大于等于其子节点的完全二叉树，最大的元素在根节点，而小顶堆是每个节点都小于等于其父节点的完全二叉树，最小的元素在根节点。在实现中，大顶堆和小顶堆都需要维护堆的性质，即父节点与其子节点之间的大小关系。

四、大根堆和大顶堆的区别

大根堆和大顶堆都是指每个节点都大于等于其子节点的完全二叉树，最大的元素在根节点，但是在实现细节上有所不同。大顶堆采用的是数组实现，而大根堆采用的是二叉搜索树实现，因此插入和删除元素时，大根堆要做平衡调整。

五、大顶堆和小根堆的区别

小根堆是一种每个节点都小于等于其子节点的完全二叉树，最小的元素在根节点，与大顶堆相反。在实现中，小根堆和大顶堆都需要维护堆的性质，即父节点与其子节点之间的大小关系。

六、大根堆和小顶堆图解

大根堆和小顶堆的结构图如下：

七、构建大顶堆

大顶堆的构建过程一般采用从最后一个非叶子节点开始进行向下调整的方式，通过不断比较父节点和其子节点的大小关系进行调整，确保每个节点都大于等于其子节点。例如，以下是构建大顶堆的代码实现：

void buildMaxHeap(int *arr, int len)
{
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        adjustDown(arr, i, len);
    }
}

八、构造大顶堆

构造大顶堆的过程就是不断将堆中最大的元素移动到堆顶，保证堆性质不变。具体实现可以通过将堆尾元素和堆顶元素进行交换，然后将堆顶元素向下调整。例如，以下是构造大顶堆的代码实现：

void heapSort(int *arr, int len)
{
    // 构建大顶堆
    buildMaxHeap(arr, len);

    // 不断取出堆顶元素放到数组末尾
    for (int i = len - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        adjustDown(arr, 0, i);
    }
}

九、初始堆是大顶堆还是小顶堆

初始堆是指构建堆前的数组，可以是乱序排列的元素。默认情况下，STL中提供的堆函数是大顶堆。如果想要构建小顶堆，需要在函数中传入比较函数greater。

十、大顶堆建堆过程图示

以下是从数组构建大顶堆的过程示意图，可以清晰地看出每一步的调整过程。

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/153127.html