基于堆的优先队列

╰+哭是因爲堅強的太久メ 2022-04-12 08:39 230阅读 0赞

与传统队列（FIFO）不同，优先队列有两种特殊的操作：**删除最大元素和插入元素**。假设有一亿个不重复的数，现在从中删除最大数，如果没有优先队列的参与，可能先要遍历这一亿个数，然后标记最大的数，最后再删掉它。那如果还要继续删除第二大的数，那么还需遍历九千九百九十九万九千九百九十九个数，效率极低。可能你会想，对这一亿个数排序就行了。但是如果这时要插入一个数进来，那又得再遍历数组甚至再进行排序，效率也极低。这时，优先队列就能高效地实现上述操作了。

堆是一种优雅的数据结构，它通常是一个可以被看做一棵树的数组对象， 堆中某个节点的值总是不大于或不小于其父节点的值。 我们可以使用二叉堆来实现优先队列。二叉堆定义如下：**二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父节点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。**

**由二叉树的性质可知，按层次从左到右为节点编号，若父节点的编号为k，则其左右子节点的编号分别为2k，2k+1。堆通常用数组来表示，且根节点的下标为1（便于计算）。以最大堆为例，如下图所示：**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70][]

可以验证一下，上面这颗二叉树是一个很漂亮的最大堆。

二叉树的性质使得我们可以很容易地通过下标去操作堆：寻找k的父节点：\[k/2\]，左右子节点：\[2k\]，\[2k+1\]。

**以最大堆为例，当堆的结构被破坏（某个父节点键值不大于子节点或子节点的键值大于了父节点时），我们就需要调整堆的结构来修复它。定义pq\[\]为基于堆的优先队列数组。**

**如果堆的有序状态因为某个节点大于其父节点而被打破时，我们就需要通过交换它和它的父节点来修复堆，这个操作称为“上浮（swim）”。通过循环不断交换当前节点与父节点直到其键值不大于父节点为止。**

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

上浮示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 1][]

**相反，当某个节点的键值小于其子节点的键值时，我们要交换它和它的较大子节点来修复堆，直到对有序。这个操作形象化地称为“下沉（sink）”。**

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

下沉示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 2][]

**当我们需要插入一个元素时，总是把它加到数组末尾（最后一个叶子节点），然后令其上浮到合适的位置。**

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

插入示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 3][]

**当我们要删除最大元素时，总是将它（根节点）与最后一个叶子节点交换，然后使新的根节点下沉到合适的位置，并将最后一个叶子节点置空。**

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

删除最大元素示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 4][]

**算法分析：因为节点数为N的二叉树的高度小于等于lgN，所以对于二叉堆实现优先队列的插入和删除最大元素来说，用时仅和队列的大小成对数关系。**

演示代码：

public class HeapPQ<Key extends Comparable<Key>> {
    	private Key[] pq;
    	private int N = 0;
    	
    	public HeapPQ(int maxN) {
    		pq = (Key[]) new Comparable[maxN+1];
    	}
    	
    	public boolean isEmpty() {
    		return N == 0;
    	}
    	
    	public int size() {
    		return N;
    	}
    	
    	public void insert(Key v) {
    		pq[++N] = v;
    		swim(pq, N);
    	}
    	
    	public Key delMax() {
    		Key max = pq[1];
    		exch(pq, 1, N--);
    		pq[N+1] = null;
    		sink(pq, 1);
    		return max;
    	}
    	
    	private static boolean less(Comparable v, Comparable w){
    		return v.compareTo(w)<0;
    	}
    	
    	private static void exch(Comparable[] pq, int i, int j) {
    		Comparable temp = pq[i];
    		pq[i] = pq[j];
    		pq[j] = temp;
    	}
    	
    	private void swim(Comparable[] pq, int k) {
    		while (k > 1 && less(pq[k/2], pq[k])) {
    			exch(pq, k/2, k);
    			k /= 2;
    		}
    	}
    	
    	private void sink(Comparable[] pq, int k) {
    		while (k*2 <= N) {
    			int j = k*2;
    			if (j < N && less(pq[j], pq[j+1]))
    				j++;
    			if (!less(pq[k], pq[j]))
    				break;
    			exch(pq, k, j);
    			k = j;
    		}
    	}
    	
    	public static void main(String[] args) {
    		int N = 10;
    		HeapPQ hp = new HeapPQ(N);
    		for (int i = 0; i < N; i++) {
    			hp.insert(N-i);
    		}
    		
    		System.out.println("HeapPQ:");
    		for (int i = 1; i <= N; i++) {
    			System.out.print(hp.pq[i]+" ");
    		}
    		System.out.println("\n");
    		
    		for (int i = 0; i < N; i++) {
    			System.out.println("delMax from hp.pq[]:"+hp.delMax());
    			for (int j = 1; j <= hp.size(); j++) {
    				System.out.print(hp.pq[j]+" ");
    			}
    			System.out.println("\n");
    		}
    	}
    }

删除最大元素测试结果（插入操作可自行测试）：

HeapPQ:
    10 9 8 7 6 5 4 3 2 1 
    
    delMax from hp.pq[]:10
    9 7 8 3 6 5 4 1 2 
    
    delMax from hp.pq[]:9
    8 7 5 3 6 2 4 1 
    
    delMax from hp.pq[]:8
    7 6 5 3 1 2 4 
    
    delMax from hp.pq[]:7
    6 4 5 3 1 2 
    
    delMax from hp.pq[]:6
    5 4 2 3 1 
    
    delMax from hp.pq[]:5
    4 3 2 1 
    
    delMax from hp.pq[]:4
    3 1 2 
    
    delMax from hp.pq[]:3
    2 1 
    
    delMax from hp.pq[]:2
    1 
    
    delMax from hp.pq[]:1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70]: /images/20220412/2bd73f2d816c403d9b2a3f0e36730b75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 1]: /images/20220412/ff64c1bd581447d39b35687614469467.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 2]: /images/20220412/d93be11e74f74b54bd63593a2677b1c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 3]: /images/20220412/c1be9d26a87044a59059b5e1e4402ee8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70 4]: /images/20220412/4bb32153515c49e6b5295165f37359f0.png