堆是完全二叉树的分布逻辑，结构可以用数组或树等实现。在完全二叉树的基础上，加上父节点优先级始终大于子节点优先级的规则，是一种弱序结构。
堆一般用于优先级存储结构，插入和删除根节点比较方便，但是查找、顺序遍历和删除其他关键字节点就不爽了。
堆排序是一种与快排复杂度相同O(NlogN)的排序，效率略低于快排，但是它很稳定，不受数据分布影响，而快排最差效率可降低到O(N*N)。
1，基于数组的堆import java.util.Random;class Item { int data; public Item(int data) { this.data = data; }}public class Heap { private Item[] array; private int maxSize; private int curSize; public Heap(int size) { maxSize = size; curSize = 0; array = new Item[size]; } public boolean insert(int key) { if (curSize == maxSize) return false; array[curSize] = new Item(key); trickleUp(curSize++); return true; } private void trickleUp(int index) { Item bottom = array[index];// 把这个要插入的先提出来 int parent = (index - 1) / 2;// 父节点索引 while (index > 0 && array[parent].data < bottom.data) { array[index] = array[parent];// 父节点下移 index = parent; parent = (parent - 1) / 2; } array[index] = bottom; } public Item remove() { Item root = array[0]; array[0] = array[--curSize]; trickleDown(0); return root; } private void trickleDown(int index) { Item top = array[index]; int large; while (index < curSize / 2) {// 此时至少一个子节点 int left = 2 * index + 1; int right = left + 1; // 包含了有无右节点2种情况 if (right < curSize && array[right].data > array[left].data) large = right; else large = left; if (top.data >= array[large].data) break; array[index] = array[large]; index = large; } array[index] = top; }//改变节点优先级 public boolean change(int index, int newValue) { if (index < 0 || index >= curSize) return false; int oldData = array[index].data; if (newValue > oldData) trickleUp(index); else trickleDown(index); return true; }//逐层显示，格式没调的好看 public void display() { int n = 1; while (true) { for (int i = n - 1; i < 2 * n - 1; i++) { if (i >= curSize) { System.out.println("\n---------------------------------"); return; } System.out.print(array[i].data + " "); } System.out.println(); n *= 2; }
}
//堆排序
public void sort(Item[] beforeSort){ array=beforeSort; maxSize=curSize=beforeSort.length; for(int i=0;i<maxSize;i++) System.out.print(array[i].data+"/"); System.out.println(); //对含有子节点的节点向下调整，一直调整到根，就将无序数组转换成了堆 for(int j=maxSize/2-1;j>=0;j--) trickleDown(j); //每次将最高优先级的数据按从数组末端到数组开头的顺序放进去，这样排序不需要第二个数组，直接将无序数组转变成有序数组 for(int k=maxSize-1;k>0;k--){ array[k]=remove();
}
//排序后输出
for(int i=0;i<maxSize;i++) System.out.print(array[i].data+"/"); System.out.println(); } public static void main(String[] args) { Heap heap = new Heap(31); Random rand = new Random(); for (int i = 0; i < 20; i++) heap.insert(rand.nextInt(100)); heap.display(); heap.remove(); heap.display(); }}
2，使用树构建堆，称为树堆import java.util.ArrayList;import java.util.List;import java.util.Random;//问题在于找到树的最后一个节点的位置（插入及删除）class Node { Node parent; Node left; Node right; int data; public Node(int data) { this.data = data; parent = null; left = null; right = null; }}class TreeHeap { Node root; int size; public TreeHeap() { root = null; size = 0; } public void insert(int key) { Node current = root;
Node temp = null;
//得到要插入位置的信息（逆序的）：如要插入位置为1011，表示从根节点到插入位置是右左右右的方向
List<Integer> list = sizeToCode(++size);
//从list倒数第二个开始遍历到首个，就是位置的信息
for (int i = list.size() - 2; i >= 0; i--) { temp = current; if (list.remove(i) == 1)//1就向右，0向左 current = current.right; else current = current.left; } if (current == root)//第一次插入 root = new Node(key); else { current = new Node(key); current.parent = temp; if (size % 2 == 0) temp.left = current; else temp.right = current; thickleUp(current);//跟第一种方法类似的调整 } } // 改变节点数据即可 private void thickleUp(Node node) { Node temp = node; while (node != root) { if (temp.data > node.parent.data) { node.data = node.parent.data; node = node.parent; } else break; } node.data = temp.data; } public Node remove() { if (size == 0) return null; Node temp = root; Node current = root; List<Integer> list = sizeToCode(size); for (int i = list.size() - 2; i >= 0; i--) { if (list.remove(i) == 1) current = current.right; else current = current.left; } if (current == root) {// size=1 root = null; size--; } else { root.data = current.data; current = null; size--; thickleDown(root); } return temp; } private void thickleDown(Node node) { int key = node.data; Node large;
while (node != null) {
if (node.left != null && node.right != null) { if (node.left.data > node.right.data) large = node.left; else large = node.right; if (key >= large.data) break; else { node.data = large.data; node = large; } } else if (node.left != null) { if (key >= node.left.data) break; else { node.data = node.left.data; node = node.left; } } else if (node.right != null) { if (key >= node.right.data) break; else { node.data = node.right.data; node = node.right; } } else break; } node.data = key; } // 找出最后一个节点所处位置，通过树的大小，将其转换成二进制编码， // 如第5个节点，5对应二进制101，去掉开头的1，即左右即是它的位置 // 此时返回的是逆序的，遍历的时候倒过来即可 public List<Integer> sizeToCode(int size) { List<Integer> list = new ArrayList<Integer>(); while (size >= 1) { list.add(size % 2); size = size / 2; } return list; } public static void main(String[] args) { TreeHeap heap = new TreeHeap(); Random rand = new Random(137); int[] array = new int[20]; for (int i = 0; i < 20; i++) { array[i] = rand.nextInt(1000); } for (int a : array) heap.insert(a); while (heap.size > 0) { System.out.print(heap.remove().data + "/"); } }}
