欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先队列和堆

程序员文章站 2024-02-15 21:38:46
...

优先队列和堆

1、优先队列

能够完成一下操作的队列叫优先队列:
1. 插入一个数值
2. 取出最小的数值(获得值并删除)

能够使用二叉高效解决上述问题的,是一种叫做堆(实际上堆有不同的数据结构,这里叫做二叉堆的数据结构)的数据结构。

2、堆的结构

堆的结构为二叉树:
堆的主要二叉树特性为:
1、所有的儿子节点的值一定不小于父亲节点值。
2、树的节点是重上到下,从左往右的顺序紧凑排列的。

向堆中插入数值,其首先将插入值放在二叉树末尾,然后根据其值的大小往上移动。
优先队列和堆

优先队列和堆

优先队列和堆

优先队列和堆

优先队列和堆

上面的一组图片展示了如何插入数据。很明显的是每次插入并调整堆后,堆的顶端保持为最小值的节点。
当我们取出最小根后,再次调整堆。

堆的复杂度

堆的加入和取出操作花费时间都和堆的深度成正比。如果有n个元素,那么每个操作可以O(logn)的时间内完成。

堆的实现

我们采用数组来存储二叉树。儿子节点满足一下性质:

  1. 左儿子的编号为自己编号×2+1;
  2. 右儿子的编号为自己编号×2+2;

优先队列和堆

#include <iostream>

#define MAX_N 1000

using namespace std;

class ArrayHeap {

private:
    int heap[MAX_N], sz = 0;

public:


    void push(int x) {
        int i = sz++; //i表示加入的节点的编号
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] <= x) break;  //不用调整

            heap[i] = heap[p];
            i = p;
        }
        heap[i] = x;
    }


    int pop() { //pop操作时,将最后一层的最右边一个节点x取出,重新调整各节点将x安放在合适的位置
        int ret = heap[0];
        int x = heap[--sz]; //sz表示个数,而数组是从0号开始,所以--sz
        //从根开始向下交换
        int i = 0;
        while (i * 2 + 1 < sz) {  //此条件表白i号结点的左右孩子都存在,左孩子小于sz表明右孩子小于或等于sz
            int lc = i * 2 + 1, rc = i * 2 + 2; //lc,rc分别为左右孩子的标号。
            if (rc < sz && heap[rc] < heap[lc]) lc = rc;  //将较小的孩子节点编号给lc

            if (heap[lc] >= x) break; //如果已经没有大小颠倒

            heap[i] = heap[lc]; //将较小的提上来
            i = lc;
        }
        heap[i] = x;

        return ret;
    }
};

实际使用中我们大可不必自己编写堆的实现,在c++标准模板库STL中已经为我们准备了priority_queue类,该类为大根堆,即每次取出的都是最大值。

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int main(){

    priority_queue<int> pque;

    srand((unsigned)time(NULL));
   for(int i=0;i<100;i++){
       pque.push(rand()%100);
   }


  while(!pque.empty()){
      cout<<pque.top()<<"\t";
      pque.pop();
  }

    return 0;
}