有时候不是所有的数据都需要完全排序,可以选择一些优先级的数据来处理.例如支持,删除最大元素和插入元素,这种数据叫优先队列.优先队列的使用和队列或栈相同,但是更高效,实现更具有挑战性.
2.4.1 API
优先队列是一种抽象数据类型,最重要的操作就是删除最大元素和插入元素.
优先队列使用场景: 输入N个字符串,每个字符串都映射一个整数,任务是找出里面的最大或者最少的M个整数(及其字符串).在某些场景中输入量可能是非常巨大,甚至认为是无限输入的.解决的方法??
因为数据量之巨大,所以无法进行重新排序,然后在筛选;所以只能依靠一种插入时即可以进行排序,然后可以delMin的方法.
这就是堆排序.
2.4.3 堆的定义
在二叉堆的数组中,每个元素都要保证大于或等于其子节点,这些位置的元素又要大于或等于数组中的另外两元素,以此类推.
定义:
当一颗二叉树的每个节点都大于等于他的两个子节点时,称堆有序.
相应的么个堆有序的二叉树中,每个节点都小于等于他的父节点;从任意节点向上都能找到非递减的元素,而从任意节点向下,都能找到非递增的元素.
命题O:
根节点是堆有序二叉树的最大节点.
用完全二叉树表达非常方便,只需要数组,不需要指针就可以表示堆有序二叉树.
定义:
二叉堆是能用堆有序的完全二叉树排序的元素,并在数组中按层级储存(不适用数组的第一个位置).二叉堆简单起见,称堆.
在堆中,K节点的父节点位置为K/2,其两个子节点为 2K ,和2K+1.
用堆存储,能实现对数级别的插入数据和删除最大元素.
命题P:
一颗大小N的完全二叉树高度为lgN.
表示一个大小为N的堆,不会使用pq[0],数据放置在pq[1]~pq[N]中. 因为考虑到 顶点和左右子节点的关系,N2,N2+1 (所以考虑N≠0)
2.4.1 由下至上的堆有序化(上浮)
需要保证,比父节点小与或等于即可,如果比父节点大,则交换父节点;然后继续比较父节点与他的前k/2元素大小.
private void swim(int k){
while(k>1&&arr[k]>arr[k/2]){
swap(k,k/2);
k=k/2;
}
}
2.4.2 由上至下的堆有序化(下沉)
private void sink(int k){
while(2k<=N){
int j=2k;
if(j<N&&arr[j]<arr[j+1]){
j++;
}
if(arr[k]>=arr[j]){
break; }
swap(k,maxIndx);
k=maxIndx;
}
}
堆的插入和删除正好是利用swim,和shink 来实现堆重拍序.
插入元素
增加堆的大小,在数组尾部增加一个元素,增加堆大小,并且利用swim(),将尾部的元素上浮到合适的位置.
删除元素
删除数组最顶部(数组左边arr[1])的元素减去一个对大小,并且把数组尾部的元素调整到最顶部(左边 arr[1]),对顶部的新元素进行shink下沉到合适的位置.
image.png
代码如下:
package algorithm.sortAlgorithm.PriortyQueen;
/**
* Created by leon on 18-1-27.
*/
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] prioryQueen;
private int node = 0;
public MaxPQ(int max) {
prioryQueen = (Key[]) new Comparable[max + 1];
}
public boolean isEmpty() {
return node == 0;package
}
public int size() {
return node;
}
public void insert(Key v) {
prioryQueen[++node] = v;
swim(node);
}
public Key delMax() {
if (isEmpty()) {
return null;
}
Key max = prioryQueen[1];
swap(1, node--);
prioryQueen[node + 1] = null;
shink(1);
return max;
}
private boolean isLess(int i, int j) {
return prioryQueen[i].compareTo(prioryQueen[j]) < 0;
}
private void swap(int i, int j) {
Key temp = prioryQueen[i];
prioryQueen[j] = prioryQueen[i];
prioryQueen[i] = temp;
}
/**
* 上浮 ,因为 如果插入的是 左节点或者右节点 k/2都是它的顶点.
*
* @param k
*/
private void swim(int k) {
while (k > 1 && isLess(k / 2, k)) {
swap(k / 2, k);
k = k / 2;
}
}
/**
* k作为 顶点,需要考虑 顶点与他的 左右子节点的大小,
*
* @param k
*/
private void shink(int k) {
while (2 * k <= node) {
//这里有一个技巧,先引入一个j,记录左右子节点最大的节点号,
// 同时判断下是否存在2k+1 的右子节点
int j = 2 * k;
if ((2 * k + 1) <= node && isLess(2 * k, 2 * k + 1)) {
j++;
}
if (!isLess(k, j)) {
break;
}
swap(k, j);
k = j;
}
}
}
命题Q:
对于一个长度为N的元素基于堆的优先队列,插入一个元素,不超过(lgN+1)次比较;删除最大元素不会超过2lgN次比较.
对于需要大量插入和删除最大元素的操作的典型数据来说,命题Q是一个重要性的突破.因为使用有序或者无序的数组来存储元素总需要 线性级别时间完成这种操作,而用堆排序的优先队列则需要对数级别时间.
2.4.4.3多叉堆
可以采用多叉堆来扩展堆排序优先队列,例如:3叉堆 使得k节点 >=[3k-1,3k,3k+1] ,k节点<=(k+1)3.
扩展下,对于任意R叉堆,都会满足下面的性质.对于 k节点:
- parent(k)节点=(k+R-2)/R
- farLeft(k) 最左子节点:farLeft=(k-1)*R+2
- farRight(k)最右子节点 =k*R+1
2.4.4.4带索引优先队列
因为优先队列不能直接访问在优先队列中的对象,并更新他们.所以出现了一种更加方便的优先队列-→索引.优先队列.
索引优先队列.我们创建两个数组分别是pq，elements。elements的作用是存储对象的引用，我们将每个对象存储在与之相关的整数作为下标的位置中，elements存储的对象不一定在数组中连续存放。pq存储是与对象相关的整数值，注意数组pq是连续存放的。此时pq作为优先队列，但是在上浮和下沉操作中，我们比较的是pq中值作为下标的elements数组中的值。这样我们就可以实现快速索引。
下图中，我们以字符串作为存储的对象类型，建立一个索引优先队列
image.png
从中我们可以看出，我们设计数组pq数组的目的。我们只需要对pq中的数值进行维护就可以实现一个优先队列，而elements中的对象的位置保持不变（出列时会置为null），这样就可以方便我们快速索引。比如通过elements数组我们可以知道与整数3相关的字符串为“f”。
在图中，我们插入一个与整数10相关的字符串“b”后，pq和elements中的值如下图所示。
image.png
假设在上图的基础上，我们要将与整数3相关的字符串修改为“a”，那么我们只需要让elements[3] = “a”即可。然后去维护pq中的值。但是在维护pq中的值时出现了一个问题，我们不知道pq中哪个位置中的值为3，只能从都到尾遍历，找到这个元素所在的位置后进行上浮和下沉操作（因为我们必须通过下标才能快速找到父节点或者孩子节点）。为了能够快速找到****pq****中元素值对应的下标，我们需要额外设置一个数组****qp****，它的作用是存储与对象相关的整数在****pq****数组中的下标，并在上浮和下沉的过程中同时维护它。
image.jpeg
在上述的基础上，假设我们需要将与整数3相关的字符串修改为“a”，那么我们只需要让elements[3] = “a”，然后通过qp[3]中的值2就可以知道数组pq中值为3的下标为2，然后对pq[2]进行上浮或下沉操作。这里显然需要进行上浮操作，那么我们要交换pq[1]和pq[2]的值。这个时候我们需要注意的是，在交换pq数组中的两个元素的值时，我们也需要交换qp对应两个元素的值，因为与对象相关的整数在pq的不同位置上，那么显然该整数在pq所在的下标也变了，所以qp中的值也应该发生变化。而需要交换的qp中的两元素的下标正好就是pq中两元素的值。结果如下图所示。所以我们也需要交换qp[3]和qp[10]的值。
image.jpeg
/*************************************************************************
* Compilation: javac IndexMinPQ.java
* Execution: java IndexMinPQ
*
* Indexed PQ implementation using a binary heap.
*
*********************************************************************/
import java.util.Iterator;
import java.util.NoSuchElementException;
public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
private int N; // number of elements on PQ
private int[] pq; // binary heap using 1-based indexing
private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
private Key[] keys; // keys[i] = priority of i
public IndexMinPQ(int NMAX) {
keys = (Key[]) new Comparable[NMAX + 1]; // make this of length NMAX??
pq = new int[NMAX + 1];
qp = new int[NMAX + 1]; // make this of length NMAX??
for (int i = 0; i <= NMAX; i++) qp[i] = -1;
}
// is the priority queue empty?
public boolean isEmpty() { return N == 0; }
// is k an index on the priority queue?
public boolean contains(int k) {
return qp[k] != -1;
}
// number of keys in the priority queue
public int size() {
return N;
}
// associate key with index k
public void insert(int k, Key key) {
if (contains(k)) throw new RuntimeException("item is already in pq");
N++;
qp[k] = N;
pq[N] = k;
keys[k] = key;
swim(N);
}
// return the index associated with a minimal key
public int min() {
if (N == 0) throw new RuntimeException("Priority queue underflow");
return pq[1];
}
// return a minimal key
public Key minKey() {
if (N == 0) throw new RuntimeException("Priority queue underflow");
return keys[pq[1]];
}
// delete a minimal key and returns its associated index
public int delMin() {
if (N == 0) throw new RuntimeException("Priority queue underflow");
int min = pq[1];
exch(1, N--);
sink(1);
qp[min] = -1; // delete
keys[pq[N+1]] = null; // to help with garbage collection
pq[N+1] = -1; // not needed
return min;
}
/*
// change key associated with index k; insert if index k is not present
public void put(int k, Key key) {
if (!contains(k)) insert(k, key);
else changeKey(k, key);
}
// return key associated with index k
public Key get(int k) {
if (!contains(k)) throw new RuntimeException("item is not in pq");
else return keys[pq[k]];
}
*/
// change the key associated with index k
public void change(int k, Key key) {
if (!contains(k)) throw new RuntimeException("item is not in pq");
keys[k] = key;
swim(qp[k]);
sink(qp[k]);
}
// decrease the key associated with index k
public void decrease(int k, Key key) {
if (!contains(k)) throw new RuntimeException("item is not in pq");
if (keys[k].compareTo(key) <= 0) throw new RuntimeException("illegal decrease");
keys[k] = key;
swim(qp[k]);
}
// increase the key associated with index k
public void increase(int k, Key key) {
if (!contains(k)) throw new RuntimeException("item is not in pq");
if (keys[k].compareTo(key) >= 0) throw new RuntimeException("illegal decrease");
keys[k] = key;
sink(qp[k]);
}
/**************************************************************
* General helper functions
**************************************************************/
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
private void exch(int i, int j) {
int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap;
qp[pq[i]] = i; qp[pq[j]] = j;
}
/**************************************************************
* Heap helper functions
**************************************************************/
private void swim(int k) {
while (k > 1 && greater(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && greater(j, j+1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}
/***********************************************************************
* Iterators
**********************************************************************/
/**
* Return an iterator that iterates over all of the elements on the
* priority queue in ascending order.
* <p>
* The iterator doesn't implement <tt>remove()</tt> since it's optional.
*/
public Iterator<Integer> iterator() { return new HeapIterator(); }
private class HeapIterator implements Iterator<Integer> {
// create a new pq
private IndexMinPQ<Key> copy;
// add all elements to copy of heap
// takes linear time since already in heap order so no keys move
public HeapIterator() {
copy = new IndexMinPQ<Key>(pq.length - 1);
for (int i = 1; i <= N; i++)
copy.insert(pq[i], keys[pq[i]]);
}
public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }
public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}
public static void main(String[] args) {
// insert a bunch of strings
String[] strings = { "it", "was", "the", "best", "of", "times", "it", "was", "the", "worst" };
IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length);
for (int i = 0; i < strings.length; i++) {
pq.insert(i, strings[i]);
}
// delete and print each key
while (!pq.isEmpty()) {
int i = pq.delMin();
StdOut.println(i + " " + strings[i]);
}
StdOut.println();
// reinsert the same strings
for (int i = 0; i < strings.length; i++) {
pq.insert(i, strings[i]);
}
// print each key using the iterator
for (int i : pq) {
StdOut.println(i + " " + strings[i]);
}
while (!pq.isEmpty()) {
pq.delMin();
}
}
}
2.4.5堆排序
我们可以把任意的优先队列变成一种排序方法.例如用最小优先队列进行,按从小到大的排序.
只需要每次取最小的元素,然后删除,把最小的元素进行重排序.这样的方法就是堆排序.
堆排序分两个阶段:
1.构造堆
2.提取,删除最小值,重拍序.
构造堆的方法: 2种:
- 1.对于未知长度的元素(动态添加元素)来构造堆,一般采用swim (上浮法)时间复杂度NlgN
- 2.对于已知长度的元素(静态元素),一般采用shink(下沉法)
1.用swim方法构造堆,相当于把数据插入到数组的尾部,然后遍历swim上浮,比较arr[k/2]与arr[k]大小,如果刚好arr[k/2]>=arr[k]就停止,否则交换位置,继续比较arr[k/2] arr[(k/2)/2]大小,直到k>1.
2.用shink的方法,从最后一棵数的 顶点开始构造.因为在优先队列中,堆的parent,和left,Child,rightChild的关系有 k, 2K,2K+1. 所以最后一棵二叉数的parent的是数组的 1/2处.
分析下shink方法的时间复杂度:O(N)
image.png
假设树的高度为h,整个树的个数为n.
考察最底层,因为最底层有可能只有一个叶子,也可能全部布满了叶子.
所以 2h≤n≤2h+1-1<2h+1 //有高度为h时最大数量为 2h+1-1
分析:h≤lgn＜h+1,所以得出,
结论1:
一个N个元素的树,高度为lgN 向下取整.
我们再来看我们分析的第二个结论。对应树每一个高度的一层，该有多少个元素呢？假设高度为1的那一层他们的元素个数为k，那么他们的访问时间复杂度为O(k)。根据前面的分析，我们还发现一个情况，就是如果从根结点开始计数，往下第i层的元素如果不是最后一层的话，这一层的元素数量为2**i(2的i次方)。正好这个第i层就相当于树的总高度减去当前层的结点的高度。假设第i层的高度为h，那么也就是i = lgn - h。
结论2：
这一层的元素数量为：
image.jpeg
那么他们所有元素的运算时间总和为如下：
image.jpeg
根据如下公式：
image.jpeg
则有：
image.jpeg
现在，我们发现，buildMaxHeap方法的时间复杂度实际上为O(n).
而swim构造堆的时间复杂度为O(NlgN)
分析Swim 方式的时间复杂度:先分析最优情况,也就一次刚好比parent小,不需要重排.时间复杂度就是常数1次O(N);最坏情况,直到最顶层的父节点才比较完长度为lgN.
image.png
堆排序的代码
package algorithm.sortAlgorithm.PriortyQueen;
import algorithm.sortAlgorithm.StdOut;
/*************************************************************************
* Compilation: javac Heap.java
* Execution: java Heap < input.txt
* Dependencies: StdOut.java StdIn.java
* Data files: http://algs4.cs.princeton.edu/24pq/tiny.txt
* http://algs4.cs.princeton.edu/24pq/words3.txt
*
* Sorts a sequence of strings from standard input using heapsort.
*
* % more tiny.txt
* S O R T E X A M P L E
*
* % java Heap < tiny.txt
* S O R T E X A M P L E A [ one string per line ]
*
* % more words3.txt
* bed bug dad yes zoo ... all bad yet
*
* % java Heap < words3.txt
* all bad bed bug dad ... yes yet zoo [ one string per line ]
*
*************************************************************************/
public class Heap {
public static void sort(Comparable[] pq) {
int N = pq.length;
for (int k = N / 2; k >= 1; k--)
sink(pq, k, N);
while (N > 1) {
exch(pq, 1, N--);
sink(pq, 1, N);
}
}
/***********************************************************************
* Helper functions to restore the heap invariant.
**********************************************************************/
private static void sink(Comparable[] pq, int k, int N) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(pq, j, j + 1)) j++;
if (!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}
/***********************************************************************
* Helper functions for comparisons and swaps.
* Indices are "off-by-one" to support 1-based indexing.
**********************************************************************/
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i - 1].compareTo(pq[j - 1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i - 1];
pq[i - 1] = pq[j - 1];
pq[j - 1] = swap;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
/***********************************************************************
* Check if array is sorted - useful for debugging
***********************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (less(a[i], a[i - 1])) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
}
优先队列的作用:
1.如果有海量数据,希望寻找Top10的元素,因为数据量太大,无法排序,因此可以只构造一个大小为10的优先队列,数据小于前10个数自动丢弃.
2.可以实现在常数时间级寻找最大数
网友评论