堆分为大顶堆，和小顶堆。 什么是堆？ 堆可以看成是一棵二叉树，二叉树的元素是一个数组不断的从左到右轮训放置。如果是大顶堆，则大的数放上面一层，小的数放下面一层。上一层的数，一定大于下一层的数。小顶堆则相反。
那么，如何实现一个大顶堆？这里我用一个链表来实现。
实现堆很简单，只要牢记他的原理就行了。
添加新元素：添加至数组末尾。然后对这个末尾节点不断的向上层冒泡。直到找到一个合适的节点放置。
删除元素：从数组末尾取出一个元素对当前要删除的元素进行覆盖，后删除末尾的元素。然后从当前节点不断的向下冒泡。就能找到一个合适的位置进行放置。
上层元素和下层元素之间的关系：上层元素（索引为：index ）和下层元素索引存在 2 * index + 1（左孩子节点） 2 * index + 2（右孩子节点）的关系。
实现源码：
package heap; import java.util.ArrayList;
import java.util.Iterator;
import java.util.List; import org.junit.Test; public class Heap {
private List<Integer> heapArray;
public Heap() {
super();
this.heapArray = new ArrayList();
}
//添加元素进堆
public void Push(Integer x) {
heapArray.add(x);
trickleUp(heapArray.size()-1);
}
//删除元素
public void Pop() {
heapArray.set(0, heapArray.get(heapArray.size()-1));
heapArray.remove(heapArray.size()-1);
trickleDown(0);
}
//取出根数据
public Integer Top() {
return heapArray.get(0);
}
//判断是否为空
public boolean isEmpty() {
if(Top() == null) {
return true;
}
return false;
}
//向上渗透
public void trickleUp(int index) {
int parent = (index-1) / 2;
Integer bottom = heapArray.get(index);
while(index > 0 && heapArray.get(parent) < bottom) {
heapArray.set(index, heapArray.get(parent));
index = parent;
parent = (parent - 1) / 2;
}
heapArray.set(index, bottom);
}
//向下渗透
public void trickleDown(int index) {
Integer top = heapArray.get(0);
int lagerChild;
while(index < heapArray.size()/2) {
int leftChild = index * 2 + 1;
int rightChild = index * 2 + 2;
if(rightChild < heapArray.size() && heapArray.get(leftChild) < heapArray.get(rightChild)) {
lagerChild = rightChild;
}else {
lagerChild = leftChild;
}
if(top >= heapArray.get(lagerChild)) {
break;
}
heapArray.set(index, heapArray.get(lagerChild));
index = lagerChild;
}
heapArray.set(index, top);
}
}
测试程序：
@Test
public void fun() {
Heap p = new Heap();
p.Push(20);
p.Push(30);
p.Push(15);
System.out.println(p.Top());
p.Push(90);
p.Push(35);
System.out.println(p.Top());
p.Pop();
System.out.println(p.Top());
}
测试结果：
30
90
35
堆排序：
堆排序非常简单，利用大顶堆的顶一定是堆元素里面的最大值。那么我们就可以将一系列数据存进去，再不断的取出顶元素。取除的元素就是一个排好序的元素。
源码：
public static void main(String[] args) {
Heap h = new Heap();
h.Push(2);
h.Push(1);
h.Push(4);
h.Push(6);
System.out.println(h.Top());
h.Pop();
System.out.println(h.Top());
h.Pop();
System.out.println(h.Top());
h.Pop();
System.out.println(h.Top());
}结果：
6
4
2
1
至此，堆排序就已经做好了。