数据结构之最小堆

╰半橙微兮° 2022-08-11 13:28 164阅读 0赞

package com.zhiru;
    
    /*
     * 最小堆例子
     * 优先级队列的各种实现中堆是最高效的一种
     * 把一个关键码的集合按照完全二叉树的顺序存储在一个一维数组中，
     * 且满足：K[i]<=K[2i+1]&&K[i]<=K[2i+2](就是最小堆)
     * 即最小堆根节点上的值是最小的。
     * 或者K[i]<=K[2i+1]&&K[i]<=K[2i+2](最大堆)
     */
    public class MinHeap {
    
    	private int[] heap;
    	private int maxSize;// 堆的最大容量
    	private int currentSize;// 堆目前容量
    	private static int defaultSize = 10;
    
    	MinHeap(int sz) {
    		maxSize = (defaultSize < sz ? sz : defaultSize);
    		heap = new int[maxSize];
    		currentSize = 0;//
    	}
    
    	MinHeap(int[] a) {
    		int len = a.length;
    		maxSize = (defaultSize < len ? len : defaultSize);
    		heap = new int[maxSize];
    		for (int i = 0; i < len; i++)
    			heap[i] = a[i];
    		currentSize = len;
    		int currentPos = (currentSize - 1) / 2;// 自上向下调整为堆
    		while (currentPos >= 0) {
    			siftDown(currentPos, currentSize - 1);
    			currentPos--;
    		}
    	}
    
    	// 最小堆的局部调整算法.
    	private void siftDown(int start, int m) {
    		int i, j;
    		i = start;// 开始节点
    		j = 2 * i + 1;// 开始节点的左子树
    		int temp = heap[i];
    		while (j <= m) {
    			if (j < m && heap[j] > heap[j + 1])
    				j++;// 左右子树那个小，走那边
    			if (temp <= heap[j])
    				break;// 父节点较子女结点小，跳出循环。
    			else {
    				heap[i] = heap[j];
    				i = j;
    				j = 2 * i + 1;
    			}
    		}
    		heap[i] = temp;// 回放
    	}
    
    	// 最小堆的另一种调整算法，从start开始调整到0节点
    	/*
    	 * 父节点的值小于子女的值则不交换
    	 */
    	private void siftUp(int start) {
    		int j = start;
    		int i = (j - 1) / 2;
    		int temp = heap[j];// 开始节点 值
    		while (j > 0) {
    			if (heap[i] <= temp)
    				break;// 父节点小不调整
    			else {
    				heap[j] = heap[i];
    				j = i;
    				i = (j - 1) / 2;
    			}
    		}
    		heap[j] = temp;
    	}
    
    	// 插入函数
    	public void insert(int val) {
    		if (currentSize == maxSize) {
    			prt("堆满！");
    			return;
    		}
    		heap[currentSize] = val;
    		siftUp(currentSize);
    		currentSize++;
    		prt("插入完毕！");
    	}
    
    	public int delete() {
    		if (currentSize == 0) {
    			prt("堆空！");
    			return -1;
    		}
    		int x = heap[0];
    		heap[0] = heap[currentSize - 1];// 将最后的元素填补到完全二叉树(堆)的开始(根)节点
    		currentSize--;// 堆长减一
    		siftDown(0, currentSize - 1);// 自上向下调整为堆
    		return x;
    	}
    
    	public void printHeap() {
    		if (heap != null && currentSize > 0) {
    			for (int i = 0; i < currentSize; i++) {
    				System.out.print(heap[i] + " ");
    			}
    		}
    	}
    
    	public static void prt(String s) {
    		System.out.print(s + "\n");
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		int[] a = { 53, 17, 78, 9, 45, 65, 87, 23 };
    		prt("调整前：");
    		for (int c : a) {
    			System.out.print(c + " ");
    		}
    		prt("");
    		MinHeap mh = new MinHeap(a);
    		prt("调整后：");
    		mh.printHeap();
    		mh.insert(1000);
    		prt("插入1000后：");
    		mh.printHeap();
    		prt("");
    		prt("删除" + mh.delete() + "后");
    		mh.printHeap();
    	}
    
    }

调整前：  
53 17 78 9 45 65 87 23   
调整后：  
9 17 65 23 45 78 87 53 插入完毕！  
插入1000后：  
9 17 65 23 45 78 87 53 1000   
删除9后  
17 23 65 53 45 78 87 1000