多条告白如次剧本只需引入一次
暂时这个系列的作品都挑着特殊典范的,让人暂时一亮的算法,即日的堆排序算法即是个中一个。 开始领会什么是堆,这内里堆(Heap)并不是步调中外存地区,而是一种实足二叉树表白的数据构造。 堆具备以次特性
是一个实足二叉树堆的每个节点的值必需大于即是安排树节点(大顶堆),或小于即是安排树节点(小顶堆)。大略证明下,实足二叉树是除去结果一层叶子节点外,其余的节点都有两个子树,而叶子节点不妨没有子树,大概惟有左子树。 如次图即是个大顶堆:
小顶堆
堆保存
堆由于是实足二叉树,特殊符合用数组保存,上海图书馆为大顶堆的保存情景,个中a[0]不必, a[1]为大顶堆的极点,也即是最大的数据,a[12]= 7 为左子树极点,a[12+1]= 6为右子树的极点,其余节点情景顺序类比。
堆的两种操纵
向堆插入元素
用图来表白如次:
向堆插入元素,先插入到结果一个数组元素场所,而后和本人的父节点6比拟,因为比6大不满意大顶堆的前提,以是9和6调换,而后9再和堆顶元素8比拟,又不满意大顶堆前提,连接调换,结果产生一个大顶堆,这个办法叫堆化。
简略堆顶元素
对于大顶堆来说,堆顶的元素为最大值,顺序简略堆顶元素并输入,那么即是将数字从大向小陈设了。
这内里又个本领,即是简略堆顶元素的功夫,不许径直简略,要用堆顶元素和结果一个元素做调换,而后按照堆的特性安排堆,直到满意前提。
完备代码如次:
package com.dianneng.lms;public class TestHeap { private int [] a; private int n; private int count; public TestHeap(int cap) { a = new int[cap+1]; n = cap; count = 0; } public void swap(int i,int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; return; } public void print(){ for (int i = 0; i <= count;i++) { System.out.print(a[i]+"t"); } } public int insert( int v) { if (count == n) { System.out.println("Heap is full!"); return -1; }else { a[++count] = v; int i = count; while (i/2 >0 && a[i] > a[i/2]) { swap(i,i/2); i = i/2; } } return 0; } public int removeMax() { if (count == 0) { return -1; } System.out.print(a[1]+"t"); a[1] = a[count]; --count; heapify(count,1); return 0; } private void heapify(int n, int i) { while(true) { int maxPos = i; //经过安排子树极点比拟赢得最大数节点 if (i*2 <= n && a[i] <a[i*2] ){ maxPos = i*2; } if (i*2+1 <= n && a[maxPos] < a[i*2+1]) { maxPos = i*2+1; } //仍旧是最大的不必调换了 if (maxPos == i) { break; } //须要调换 swap(i,maxPos); //i指向待调换的 i = maxPos; } } public static void main(String [] args) { TestHeap th = new TestHeap(18); th.insert(8); th.insert(7); th.insert(6); th.insert(5); th.insert(4); th.insert(3); th.print(