优先队列与二叉堆-阿里云开发者社区

开发者社区> ggbond233> 正文

优先队列与二叉堆

简介: 普通队列:先进先出,后进后出 优先队列:出队顺序和入队顺序无关,和优先级相关
+关注继续查看

优先队列

概念

普通队列:先进先出,后进后出

优先队列:出队顺序和入队顺序无关,和优先级相关

应用

  1. 动态数据:操作系统中对于任务的调度(程序的优先级是随时变化的,因此要动态的进行处理,而不是简单的排序)
  2. 静态数据:在n个元素中,选出前m个元素

不同实现的时间复杂度分析

可以使用不同的底层实现

  1. 普通数组:入队直接将元素加到末尾,出队则需要遍历数组拿到优先级最高的元素
  2. 顺序数组(不断维护数组有序性):入队时需要遍历数组找到合适的位置,出队直接出队头元素

入队出队(拿出最大元素)
普通线性结构(数组、链表)O(1)O(N)
顺序线性结构O(N)O(1)
O(logN)O(logN)

如果时间复杂度为O(logN),那么近乎一定和树有关

例:归并排序和快速排序时间复杂度都是O(nlogn),虽然排序过程没有使用树结构,但是递归的过程形成了一棵隐形的递归树

二叉堆

概念

堆也是一棵树,最主流的是用二叉树来实现,称为二叉堆

性质

  1. 二叉堆是一棵完全二叉树

完全二叉树:除了最后一层外其余层都是满的,且最后一层元素都在左边

满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树

  1. 最大堆:当前节点的值总是不大于父节点的值(左右孩子的值 <= 父节点的值)
  2. 最小堆:当前节点的值总是不小于父节点的值(左右孩子的值 >= 父节点的值)
  3. 节点的大小与节点所处的层次之间没有关联

用数组表示完全二叉树(索引之间的数学规律)

先推理出【下标从1开始】的规律,再根据这个规律去推【下标从0开始】会比较容易,因为整体骨架不变,修改细枝末节即可

  1. 数组下标从1开始

parentIndex(i)=i/2

leftIndex(i)=2*i

rightIndex(i)=2*i+1

  1. 数组下标从0开始

parentIndex(i)=(i-1)/2

leftIndex(i)=2*i+1

rightIndex(i)=2*i+2

1. Java实现

1. 成员变量(一般是声明底层数据结构)

二叉堆我们使用动态数组来实现,因此成员变量为动态数组

    //成员变量:一个动态数组

   private Array<E> data;

2. 构造方法(一般是对成员变量初始化)

    //构造方法

   public MaxHeap(int capacity){

       data=new Array<>(capacity);

   }

   public MaxHeap(){

       data=new Array<>();

   }

3. 成员方法(私有的辅助方法)

重复使用的代码,可以将其封装为辅助方法

    //私有的工具类

   //返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引(数组下标从0开始)

   private int parentIndex(int index){//传入索引,返回索引

       if (index==0)

           throw new IllegalArgumentException("index_0 doesn't have parent!");

       return (index-1)/2;

   }

   //返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引

   private int leftChildIndex(int index){

       return (index*2)+1;

   }

   //返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子的节点的索引

   private int rightChildIndex(int index){

       return (index*2)+2;

   }

4. 向堆中添加元素

先将目标节点添加到末尾,再进行上浮操作

   public void add(E e){

       //将其添加到数组

       data.addLast(e);

       //调用上浮函数

       siftUp(data.getSize()-1);

   }

   //将索引所在节点上浮到其在最大堆中合适位置

   private void siftUp(int k) {

       //k不为根节点,并且k的父节点小于k,不符合最大堆性质,将他们互换位置(直到k为根节点或者k的父节点大于等于k)

       while (k>0&&data.get(parentIndex(k)).compareTo(data.get(k))<0){

           data.swap(k, parentIndex(k));

           //更改k的索引

           k=parentIndex(k);

       }

   }

3. 从堆中取出元素

从堆中将最大值(根节点)取出,再将左右两棵子树合成堆,相对比较复杂。不如:将根节点与末尾节点交换,交换完成后,删除末尾节点,再将根节点进行下沉操作

    //查看堆中的最大值

   public E findMax(){

       if (data.getSize()==0)

           throw new IllegalArgumentException("heap is empty!");

       return data.get(0);

   }

    //提取堆中的最大值

   public E extractMax(){

       E max=findMax();

       //将最后一个元素与根节点交换,然后移除最后一个节点

       data.swap(0, data.getSize()-1);

       data.remove(data.getSize()-1);

       //在最大堆中将根节点下沉到合适位置

       siftDown(0);

       return max;

   }

   //在最大堆中将指定索引位置的节点下沉到合适位置

   private void siftDown(int k) {

       //首先判断当前节点是否还有子节点(先来判断左子树是否存在,因为左右子树还要进行比较)

       //k的左孩子的索引小于size,说明左节点存在

       while (leftChildIndex(k)<data.getSize()){

           //j为左孩子的索引

           int j=leftChildIndex(k);

           //如果右节点存在,并且右节点大于左节点,就将j赋值为右节点的索引;否则j还是左节点的索引

           if (j+1<data.getSize()&&data.get(j+1).compareTo(data.get(j))>0)

               j=rightChildIndex(k);

           //data[j]为左右节点中的最大值

           //再用当前索引节点与最大值比较

           if (data.get(k).compareTo(data.get(j))>=0)

               //当前节点大于或等于左右子节点的最大节点,符合最大堆,直接跳出循环

               break;

           //当前索引节点小于左右节点中的最大节点,将二者进行交换

           data.swap(k, j);

           //交换后对当前索引k重新赋值

           k=j;

       }

   }

4. 时间复杂度分析

向堆中添加元素、取出最大值都是O(logn)

完全二叉树不会退化成单链表

二叉树的高度级别为O(logn)

5. heapify:将任意数组整理成堆的形状(堆化)

heapify:从最后一个非叶子节点开始,依次向上进行siftdown下沉操作,直到根节点,最后形成最大堆

用数组来表示完全二叉树,如何定位最后一个非叶子节点的索引?

当数组从0开始存储:parentIndex(i)=(i-1)/2 i=data.getSize()-1 i为最后一个节点的索引

当数组从1开始存储:parentIndex(i)=i/2 i=data.getSize()

5.1 heapify的算法复杂度

  1. 将n个元素依次插入到一个空堆中,时间复杂度为O(nlogn)
  2. heapify过程的时间复杂度为O(n)

6. heapify代码

将heapify过程设置为构造函数,用户传来数组,即可生成最大堆

    //heapify的过程

   public MaxHeap(E[] arr){

       //用户传来一个数组,我们生成一个对应的动态数组

       data=new Array<>(arr);

       //从最后一个非叶子节点开始,向前遍历,依次siftdown下沉操作

       for (int i=parentIndex(data.getSize()-1);i>=0;i--)

           siftDown(i);

   }

 //Array的构造函数

 public Array(E[] arr){

        data=(E[])new Object[arr.length];

        for (int i = 0; i < arr.length; i++)

            data[i]=arr[i];

        size=arr.length;

    }

2. C++实现

#include<iostream>

#include<algorithm>

#include<cassert> 

#include<ctime>


using namespace std;


template<typename Item>

class MaxHeap {

 private:

  Item* data;

  int count;

  int capacity; 

  //上浮:将索引为k的元素上浮到合适位置

  void shiftUp(int k) {

   //与父节点比较,直到小于或等于父节点

   while(k>1&&data[k]>data[k/2]) { //当前节点data[k]大于父节点,要进行上浮,k最少在第二层才能跟父节点比较 

    swap(data[k],data[k/2]);

    k/=2;

   }

  }

  void shiftDown(int k){

   //1.首先判断是否存在孩子节点:左孩子坐标小于等于count(count是最后一个元素的索引) 

   while(2*k<=count){

    int j=2*k;//在此轮循环中data[k]与data[j]交换(data[j]代表子节点中值大的那一个) 

    //2.如果存在右孩子并且右孩子大于左孩子,j++ 

    if(j+1<=count&&data[j+1]>data[j])

     j+=1;

    //3.将位于j索引的元素与当前元素比较

    if(data[k]>=data[j])//当前节点大于等于两个子节点,说明已经到达合适位置,直接跳出循环 

     break;

    else {

     swap(data[j],data[k]);//否则,将他们进行交换,并且修改当前元素的索引 

     k=j;

    }

   }

  }  

 public:

  MaxHeap(int capacity) {

   //因为我们的数组下标从1开始

   data=new Item[capacity+1];

   count=0;

   this->capacity=capacity;

  }

  ~MaxHeap() {

   delete [] data;

  }


  int size() {

   return count;

  }

  bool isEmpty() {

   return count==0;

  }

  void insert(Item item) {

   //防止越界 

   assert(count+1<=capacity);

   //从下标1开始,把元素放到数组末尾,即在二叉堆的最后

   data[count+1]=item;

   count++;

   //shiftUp:上浮

   shiftUp(count);

  }

  //提取最大值 

  Item extractMax(){

   assert(count>0);

   //保存根节点,最后返回 

   Item ret=data[1]; 

   //将根节点与末尾节点交换

   swap(data[1],data[count]);

   count--;

   //下沉 

   shiftDown(1);

   return ret; 

  }



public:

    // 以树状打印整个堆结构

    void testPrint(){


        // 我们的testPrint只能打印100个元素以内的堆的树状信息

        if( size() >= 100 ){

            cout<<"This print function can only work for less than 100 int";

            return;

        }


        // 我们的testPrint只能处理整数信息

        if( typeid(Item) != typeid(int) ){

            cout <<"This print function can only work for int item";

            return;

        }


        cout<<"The max heap size is: "<<size()<<endl;

        cout<<"Data in the max heap: ";

        for( int i = 1 ; i <= size() ; i ++ ){

            // 我们的testPrint要求堆中的所有整数在[0, 100)的范围内

            assert( data[i] >= 0 && data[i] < 100 );

            cout<<data[i]<<" ";

        }

        cout<<endl;

        cout<<endl;


        int n = size();

        int max_level = 0;

        int number_per_level = 1;

        while( n > 0 ) {

            max_level += 1;

            n -= number_per_level;

            number_per_level *= 2;

        }


        int max_level_number = int(pow(2, max_level-1));

        int cur_tree_max_level_number = max_level_number;

        int index = 1;

        for( int level = 0 ; level < max_level ; level ++ ){

            string line1 = string(max_level_number*3-1, ' ');


            int cur_level_number = min(count-int(pow(2,level))+1,int(pow(2,level)));

            bool isLeft = true;

            for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){

                putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft );

                isLeft = !isLeft;

            }

            cout<<line1<<endl;


            if( level == max_level - 1 )

                break;


            string line2 = string(max_level_number*3-1, ' ');

            for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ )

                putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 );

            cout<<line2<<endl;


            cur_tree_max_level_number /= 2;

        }

    }


private:

    void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){


        int sub_tree_width = (cur_tree_width - 1) / 2;

        int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width;

        assert(offset + 1 < line.size());

        if( num >= 10 ) {

            line[offset + 0] = '0' + num / 10;

            line[offset + 1] = '0' + num % 10;

        }

        else{

            if( isLeft)

                line[offset + 0] = '0' + num;

            else

                line[offset + 1] = '0' + num;

        }

    }


    void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){


        int sub_tree_width = (cur_tree_width - 1) / 2;

        int sub_sub_tree_width = (sub_tree_width - 1) / 2;

        int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width;

        assert( offset_left + 1 < line.size() );

        int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width;

        assert( offset_right < line.size() );


        line[offset_left + 1] = '/';

        line[offset_right + 0] = '\\';

    }

};


int main() {

 MaxHeap<int> maxHeap(100);

 srand(time(0));

 for(int i=0;i<100;i++){

  maxHeap.insert(rand()%100);

 }

 //打印二叉堆 

// maxHeap.testPrint();

 while(!maxHeap.isEmpty()){

  cout<< maxHeap.extractMax()<<" ";

  cout <<endl;

 }

 return 0;

}

最大堆实现优先队列

queue的接口

面向接口编程:无论底层实现,接口都一样,功能都一样

public interface Queue<E> {

    int getSize();

    boolean isEmpty();

    void enqueue(E e);

    E dequeue();

    E getFront();

}

/**

 * 基于最大堆实现的优先队列

 * @param <E>

 */

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    //成员变量,一般是底层数据结构,且不对其进行初始化

    private MaxHeap<E> maxHeap;

    //构造函数

    public PriorityQueue(){

        //对成员变量初始化

        maxHeap=new MaxHeap<E>();

    }

    @Override

    public int getSize() {

        return maxHeap.size();

    }


    @Override

    public boolean isEmpty() {

        return maxHeap.isEmpty();

    }


    @Override

    public void enqueue(E e) {

        maxHeap.add(e);

    }


    @Override

    public E dequeue() {

        return maxHeap.extractMax();

    }


    @Override

    public E getFront() {

        return maxHeap.findMax();

    }

}

优先队列的应用:在n个元素中,选出前m个元素

在n个元素中,选出前m个元素?(M远小于N)

  1. 使用归并排序与快速排序:O(nlogn)
  2. 使用二叉堆:O(nlogm)

在二叉堆中存储前m个元素,下一个元素(m+1)如果大于二叉堆中的最小值,就将他们替换。

可以使用最小堆(根节点为最小值),又因为优先级是由我们(用户)定义的,所以也可以使用最大堆(数值越小越优先,则根节点为优先级最高的最小值),都可以帮助我们快速定位二叉堆中的最小值

java中的PriorityQueue内部默认是最小堆


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
4123 0
javascript实现优先队列
1.概念     一般情况下从队列中删除元素,都是率先入队的元素。但是有些使用队列的情况不遵循先进先出的原则,这就是插队,这需要使用优选队列的数据结构来进行描述。     从优先队列中删除元素的时候,需要考虑优先级的限制。
571 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4576 0
UESTC 1599 wtmsb【优先队列+排序】
题目链接:UESTC 1599 wtmsb 题意:给你一组数,每一次取出两个最小的数,将这两个数的和放入这组数中,直到这组数只剩下一个,求最后剩下那个数的大小! 分析:比赛的时候首先我就看到这道题数据是200000,跑时100ms,我把思路捋了一遍,然后讲给旁边人听,一眼看过去,lfh说用哈夫曼树吧,然后找了个板子直接扔上去了, 结果显示出这样的操作:Restricted Function on test 1,从来没见过这个错误啊,百度找了一下,发现这个错误是它oj本身不支持某些函数,比如qsort这种排序操作,wc。
802 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
9480 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
5787 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
3521 0
+关注
62
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载