首页 > 代码库 > java实现最小堆
java实现最小堆
１.堆：通常通过二叉堆，实为二叉树的一种，分为最小堆和最大堆，具有以下性质：
- 任意节点小于它的所有后裔，最小元在堆的根上。
- 堆总是一棵完全树
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
２.最小堆实现：
插入：
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 =http://www.mamicode.com/ 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 =http://www.mamicode.com/= 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 = http://www.mamicode.com/{ 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 }
java实现最小堆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。