普林斯顿算法中级笔记7(优先队列)

---

什么是优先队列

一个普通队列在删除时，删除最大或者最小的元素

方法定义

方法
MaxPQ()	创建一个空队列
MaxPQ(Key[] a)	创建一个具有初始化数据的队列
void insert(Key v)	插入
Key delMax()	删除最大元素，并返回该元素
boolean isEmpty()	是否为空
Key max()	返回最大元素
int size()	返回队列大小

二叉树(后面将之成为堆)

节点为N的二叉树，高度为lgN

大(小)顶堆

每一个父节点都不小于它的子节点

数组实现二叉树结构

以索引1作为起始，1的位置存储根结点，节点n的子节点为2n,2n+1，节点k的子节点为k/2

屏幕快照 2018-08-14 下午4.55.41.png

节点的提升

首先针对单个节点进行处理
循环比较，它与它的父节点，若大于父节点则进行交换。

private void swim(int k)
{
 while (k > 1 && less(k/2, k))
 {
 exch(k, k/2);
 k = k/2;
 }
}

节点的插入

public void insert(Key x)
{
 pq[++N] = x;
 swim(N);
}

节点的下降

若节点小于子节点，则将次节点循环下降

private void sink(int k)
{
 while (2*k <= N)
 {
 int j = 2*k;
 if (j < N && less(j, j+1)) j++;
 if (!less(k, j)) break;
 exch(k, j);
 k = j;
 }
}

删除最大元素

将最顶部元素与末尾元素交换，而后输出末尾元素，并且将交换后的顶部元素再进行sink

public Key delMax()
{
 Key max = pq[1];
 exch(1, N--);
 sink(1);
 pq[N+1] = null;
 return max;
} 

算法复杂度分析

方法	复杂度
insert	logN
delMax	logN

堆排序

思路

• 构造一个大顶堆，取堆顶元素，将堆顶元素与最后一个元素交换。
• 将剩余元素重新构成一个大顶堆

代码实现

public class Heap
{
 public static void sort(Comparable[] a)
 {
 int N = a.length;
 for (int k = N/2; k >= 1; k--)
 sink(a, k, N);
 while (N > 1)
 {
 exch(a, 1, N);
 sink(a, 1, --N);
 }
 }
}

算法复杂度与特点分析

• 堆排序的算法复杂度为2NlogN,最坏为2NlogN，最好为NlogN
• 它是一个占用额外空间很小的算法
• 它是一个不稳定算法