优先队列
概念
普通队列：先进先出，后进后出
优先队列：出队顺序和入队顺序无关，和优先级相关
应用
- 动态数据：操作系统中对于任务的调度（程序的优先级是随时变化的，因此要动态的进行处理，而不是简单的排序）
- 静态数据：在n个元素中，选出前m个元素
不同实现的时间复杂度分析
可以使用不同的底层实现
- 普通数组：入队直接将元素加到末尾，出队则需要遍历数组拿到优先级最高的元素
- 顺序数组（不断维护数组有序性）：入队时需要遍历数组找到合适的位置，出队直接出队头元素
- 堆
| 入队 | 出队(拿出最大元素) | |
| 普通线性结构(数组、链表) | O(1) | O(N) |
| 顺序线性结构 | O(N) | O(1) |
| 堆 | O(logN) | O(logN) |
如果时间复杂度为O(logN)，那么近乎一定和树有关
例：归并排序和快速排序时间复杂度都是O(nlogn)，虽然排序过程没有使用树结构，但是递归的过程形成了一棵隐形的递归树
二叉堆
概念
堆也是一棵树，最主流的是用二叉树来实现，称为二叉堆
性质
- 二叉堆是一棵完全二叉树
完全二叉树：除了最后一层外其余层都是满的，且最后一层元素都在左边
满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树
-
最大堆：当前节点的值总是不大于父节点的值（左右孩子的值 <= 父节点的值）
-
最小堆：当前节点的值总是不小于父节点的值（左右孩子的值 >= 父节点的值）
- 节点的大小与节点所处的层次之间没有关联
用数组表示完全二叉树（索引之间的数学规律）
先推理出【下标从1开始】的规律，再根据这个规律去推【下标从0开始】会比较容易，因为整体骨架不变，修改细枝末节即可
- 数组下标从1开始
parentIndex(i)=i/2
leftIndex(i)=2*i
rightIndex(i)=2*i+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的算法复杂度
- 将n个元素依次插入到一个空堆中，时间复杂度为O(nlogn)
- 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）
- 使用归并排序与快速排序：O(nlogn)
- 使用二叉堆：O(nlogm)
在二叉堆中存储前m个元素，下一个元素(m+1)如果大于二叉堆中的最小值，就将他们替换。
可以使用最小堆（根节点为最小值），又因为优先级是由我们（用户）定义的，所以也可以使用最大堆（数值越小越优先，则根节点为优先级最高的最小值），都可以帮助我们快速定位二叉堆中的最小值
java中的PriorityQueue内部默认是最小堆