java实现最小堆

浏览数：92 / 时间：2015年06月08日

１.堆：通常通过二叉堆，实为二叉树的一种，分为最小堆和最大堆，具有以下性质：

任意节点小于它的所有后裔，最小元在堆的根上。
堆总是一棵完全树

　　将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

２.最小堆实现：

　　插入：

　　1）将新插入的元素，放置到队列的尾部。

　　2）若该元素小于其父节点，两个元素互换。（上移操作）

　　3）迭代，直至该元素没有父节点或小于其父节点。

　　删除：

　　1）移掉顶部的节点。

　　2）将队末的元素放置到顶部。

　　3）该节点与其子节点中较小的那个比较，若小于它，则交换位置，（下移操作）

　　4）迭代，直到叶节点或不再比其子节点中较小那个大。

　　java　code：

 1 package minHeap;
 2 
 3public class MinHeap {
 4     private int[] data;
 5 
 6     public MinHeap(int[] data) {
 7         this.data = data;
 8     }
 9 
10     public void createHeap() {
11         for (int i = (data.length) / 2 - 1; i >= 0; i--) {
12             heapIfy(i);
13         }
14     }
15 
16     public void heapIfy(int value) {
17         int lchild = left(value);
18         int rchild = right(value);
19         int smallest = value;
20         if (lchild < data.length && data[lchild] < data[value])
21             smallest = lchild;
22         if (rchild < data.length && data[rchild] < data[smallest])
23             smallest = rchild;
24         if (value == smallest)
25             return;
26         swap(value, smallest);
27         heapIfy(smallest);
28     }
29 
30     public int left(int value) {
31         return ((value + 1) << 1) - 1;
32     }
33 
34     public int right(int value) {
35         return (value + 1) << 1;
36     }
37 
38     public void swap(int i, int j) {
39         int tmp = data[i];
40         data[i] = data[j];
41         data[j] = tmp;
42     }
43 
44     public void setRoot(int value) {
45         data[0] = value;
46         heapIfy(0);
47     }
48 
49     public static void main(String[] args) {
50         int[] value = { 10, 100, 12, 73, 45, 32, 11, 23, 55, 34, 90, 21 };
51         MinHeap heap = new MinHeap(value);
52         heap.createHeap();
53         for (int i = 0; i < value.length; i++) {
54             System.out.print(heap.data[i] + " ");
55         }
56         System.out.println();
57         heap.setRoot(64);
58         for (int i = 0; i < value.length; i++) {
59             System.out.print(heap.data[i] + " ");
60         }
61         System.out.println();
62     }
63 }