优先队列

概念

普通队列：先进先出，后进后出

优先队列：出队顺序和入队顺序无关，和优先级相关

应用

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

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

可以使用不同的底层实现

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

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

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

二叉堆

概念

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

性质

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

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

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

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

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

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

1. 数组下标从1开始
   

parentIndex(i)=i/2

leftIndex(i)=2*i

rightIndex(i)=2*i+1

2. 数组下标从0开始
   

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

leftIndex(i)=2*i+1

rightIndex(i)=2*i+2

1. Java实现

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

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

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

   privateArray<E>data;

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

   //构造方法

   publicMaxHeap(intcapacity){

       data=newArray<>(capacity);

   }

   publicMaxHeap(){

       data=newArray<>();

   }

3. 成员方法（私有的辅助方法）

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

   //私有的工具类

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

   privateintparentIndex(intindex){//传入索引，返回索引

       if (index==0)

           thrownewIllegalArgumentException("index_0 doesn't have parent!");

       return (index-1)/2;

   }

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

   privateintleftChildIndex(intindex){

       return (index*2)+1;

   }

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

   privateintrightChildIndex(intindex){

       return (index*2)+2;

   }

4. 向堆中添加元素

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

   publicvoidadd(Ee){

       //将其添加到数组

       data.addLast(e);

       //调用上浮函数

       siftUp(data.getSize()-1);

   }

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

   privatevoidsiftUp(intk) {

       //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. 从堆中取出元素

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

   //查看堆中的最大值

   publicEfindMax(){

       if (data.getSize()==0)

           thrownewIllegalArgumentException("heap is empty!");

       returndata.get(0);

   }

   //提取堆中的最大值

   publicEextractMax(){

       Emax=findMax();

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

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

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

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

       siftDown(0);

       returnmax;

   }

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

   privatevoidsiftDown(intk) {

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

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

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

           //j为左孩子的索引

           intj=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)/2i=data.getSize()-1i为最后一个节点的索引

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

5.1 heapify的算法复杂度

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

6. heapify代码

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

   //heapify的过程

   publicMaxHeap(E[] arr){

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

       data=newArray<>(arr);

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

       for (inti=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内部默认是最小堆