priority_queue的底层实现及数组建堆。

时间：2022-02-25 17:38:41


注意：

1 如果要用到小顶堆，则一般要把模板的三个参数都带进去。 STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明小顶堆

#include <iostream>
#include <queue>

using namespace std;

int main(){
    priority_queue<int, vector<int>, greater<int> > q;

    for( int i= 0; i< 10; ++i ) q.push( rand() );
    while( !q.empty() ){
        cout << q.top() << endl;
        q.pop();
    }

    getchar();
    return 0;
}

2 为了指定第三个模板参数，我们必须将前两个参数都指明出来(这是C++语法规则).



stack与queue注意事项：

1 stack不允许有遍历行为，stack也不提供迭代器。SGI STL便以deque作为缺省情况下stack底部结构，称之为adapter（配接器）

2 除了deque之外，list也是双向开口的数据结构

3 queue与stack的情况类似，不提供迭代器，也可以以list作为底层容器,默认为deque。


priority_queue的底层实现——heap


缺省情况下priority_queue优先级队列是利用一个max-heap最大堆完成，后者是一个以vector表现的完全二叉树。

“依权值高低自动递减排序”



1 priority_queue允许用户以任何次序将任何元素推入容器内，但取出时一定是从优先权最高(也即数值最高，最大堆)的元素开始取。

2 二叉堆，完全二叉树，（由数组实现，数组来存储所有节点,2*i+1,2*i+2,但是由于动态改变大小，所以不用array用vector）插入O(logN)，删除O(logN)


本人亲自实现的堆排序过程：

#include <iostream>
#include <time.h>
#include <algorithm>
using namespace std;

/*
调整堆：默认最大堆，每次调整结束后，堆顶即为最大值。
类似于：向上冒泡的过程。
*/
void maxheapfixdown(int a[], int i, int n){
    int tmp = a[i];
    int j = 2 * i + 1;
    while (j<n){
        if (j + 1<n&&a[j]<a[j + 1]) ++j;//防止数组越界，控制。
        if (a[j]<tmp)//特别注意：每次比较的是最初的tmp,而不是a[i];
            break;//这个地方不是在a[j]<a[i]时break,而是在a[j]<tmp时break;
        a[i] = a[j];
        i = j;
        j = 2 * i + 1;
    }
    a[i] = tmp;//向上冒泡结束，插入到正确的位置。
}
/*
堆排序：1. 建堆 2. n-1次调整和n-1次swap()
*/
void heap_sort(int a[], int n){

    for (int i = (n - 2) / 2; i >= 0; --i)
    {
        maxheapfixdown(a, i, n);//建堆，从末尾的第一个非叶节点，即i=(n-2)/2处开始。
    }
    for (int k = 1; k <= n - 1; ++k)//建堆时相当于完成了一次堆调整，还需要n-1次堆调整。
    {
        swap(a[0], a[n - k]);//上次调整完之后，把最大值放到末尾。
        maxheapfixdown(a, 0, n - k);
    }

}

#define N 500

int main()
{

    srand((unsigned)time(NULL));
    int a[N];
    for (int i = 0; i < N; i++)
    {
        a[i] = rand() % (N + 1);
    }

    for (int i = 0; i < N; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    cout << "********************" << endl;
    heap_sort(a, N);

    for (int i = 0; i < N; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;

    system("pause");


    return 0;
}


STL heap包括：

1 push_heap算法：新元素插入在底层的vector的end()处。向上回溯

2 pop_heap算法：把堆顶元素和数值末尾元素调换，向下回溯。

3 sort_heap算法：持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素。执行过后，原来的heap不再是个合法的heap了。

4 meak_heap算法：找出第一个需要重排的子树头部(n-2)/2，从当前位置向根节点回溯。




标签：

相关文章