堆排序应用之优先队列的实现

╰半夏微凉° 2022-08-21 02:11 142阅读 0赞

我在上一篇博客中写了堆排序。在这篇文章中我对上篇的进行了一点改变，比如说方法和实例变量的访问级别。

优先队列的定义：一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值称为关键字。

优先队列可以实现的操作有下方四个：

MAX\_HEAP\_INSERT(int key)：将值为key的元素插入集合中。

HEAP\_MAXIMUN()：返回堆中值最大的元素。

HEAP\_EXTRACT\_MAX()：去掉并返回S中的具有最大关键字的元素。

HEAP\_INCREASE\_KEY(int i, int key)：将位于i处的值变为key，且key的值大于原来的值。

具体实现代码和测试代码如下：

package algorithms;
    
    import java.util.ArrayList;
    
    public class PriorityQueue {
    	private int heap_size;
    	private ArrayList<Integer> A;
    
    	private PriorityQueue() {
    		this.A = new ArrayList<Integer>();
    		this.heap_size = 0;
    	}
    	private PriorityQueue(ArrayList<Integer> A) {
    		this.A = A;
    		this.heap_size = A.size();
    	}
    
    	private int LEFT(int i) {
    		return (i << 1) + 1; // 括号必须要，否则先做加法运算
    	}
    
    	private int RIGHT(int i) {
    		return (i << 1) + 2;
    	}
    
    	private int PARENT(int i) {
    		return (i - 1) >> 1;
    	}
    
    	private void SWAP(ArrayList<Integer> A, int i, int j) {
    		int temp = A.get(i);
    		A.set(i, A.get(j));
    		A.set(j, temp);
    		return;
    	}
    
    	public int HEAP_MAXIMUM() {
    		return A.get(0);
    	}
    
    	private void MAX_HEAPIFY(ArrayList<Integer> A, int i) {
    		int Largest = i;
    		int L = LEFT(i), R = RIGHT(i);
    		if (L < this.heap_size && A.get(L) > A.get(i)) {
    			Largest = L;
    		}
    		if (R < this.heap_size && A.get(R) > A.get(Largest)) {
    			Largest = R;
    		}
    
    		if (Largest != i) {
    			SWAP(A, i, Largest);
    			MAX_HEAPIFY(A, Largest);
    		}
    	}
    
    	public int HEAP_EXTRACT_MAX() {
    		int max = A.get(0);
    		A.set(0, A.get(this.heap_size - 1));
    		this.heap_size--;
    		MAX_HEAPIFY(A, 0);
    		A.remove(heap_size);
    		return max;
    	}
    
    	public boolean HEAP_INCREASE_KEY(int i, int key) {
    		if (key < A.get(i)) {
    			System.out.println("the new key is smaller then current key");
    			return false;
    		}
    		A.set(i, key);
    		for (int j = PARENT(i); j >= 0; j = PARENT(j)) {
    			if (key > A.get(j)) {
    				A.set(i, A.get(j));
    				i = j;
    			} else {
    				A.set(i, key);
    			}
    		}
    		if (i == 0) {
    			A.set(i, key);
    		}
    		return true;
    	}
    
    	public boolean MAX_HEAP_INSERT(int key) {
    		this.A.add(Integer.MIN_VALUE);
    		this.heap_size++;
    		return HEAP_INCREASE_KEY(this.heap_size-1, key);
    	}
    
    	public static void main(String[] args) {
    		int[] in = new int[]{16,14,10,8,7,9,3,2,0,1};
    
    		ArrayList<Integer> A = new ArrayList<Integer>();
    		for (Integer integer : in) {
    			A.add(integer);
    		}
    		for (Integer integer : A) {
    			System.out.print(integer+",");
    		}System.out.println("                 "+A.size());
    		PriorityQueue priorityQueue = new PriorityQueue(A);
    		System.out.println(priorityQueue.HEAP_MAXIMUM());
    		System.out.println(priorityQueue.HEAP_INCREASE_KEY(8, 180));
    		for (Integer integer : A) {
    			System.out.print(integer+",");
    		}System.out.println("                 "+A.size());
    		
    		System.out.println(priorityQueue.HEAP_EXTRACT_MAX());
    		for (Integer integer : A) {
    			System.out.print(integer+",");
    		}System.out.println("                 "+A.size());
    		System.out.println(priorityQueue.MAX_HEAP_INSERT(180));
    		for (Integer integer : A) {
    			System.out.print(integer+",");
    		}System.out.println("                 "+A.size());
    	}
    
    }

测试结果如下：

![20160310143956652][]

MAX\_HEAP\_INSERT(int key)的时间复杂度为O(lgn)。

HEAP\_MAXIMUN()的时间复杂度为O(1)。

HEAP\_EXTRACT\_MAX()的时间复杂度为O(lgn)，因为除了时间复杂度为O(lgn)的MAX\_HEAPIFY以外（[看我上篇博客如何求MAX\_HEAPIFY的时间复杂度][MAX_HEAPIFY]），它的其他操作都是常数阶的。

HEAP\_INCREASE\_KEY(int i, int key)的时间复杂度为O(lgn)。

最后，总之在一个包含n个元素的堆中，所有的优先队列的操作都可以在O(lgn)的时间内完成。

[20160310143956652]: /images/20220731/c716b215048f420a8d7e22a839819f3d.png
[MAX_HEAPIFY]: http://blog.csdn.net/wsyw126/article/details/50838536