1、什么是堆

现在有这么一个需求，设计一个结构，满足两个操作要求：

1. 删除时，返回该结构的最大值或者最小值的元素
2. 往结构中新增元素

问题：如何组织优先这种结构？

• 一般数组、链表？
• 有序数组或者链表？
• 二叉搜索树或者AVL树？

结构	插入	删除
数组	插到数组尾部时间复杂度O(n)	查找最大或者最小值，删除后需要移动元素，时间复杂度O(2n)
链表	插入到链表头部，时间复杂度 O(1)	查找最大或者最小值，删除结点，时间复杂度O(n)
有序数组	查找插入位置，插入后移动元素并且插入，时间复杂度O(2n)	删除尾部，时间复杂度O(1)
有序链表	查找插入位置，插入节点，时间复杂度O(n)	删除首或者尾节点，时间复杂度O(1)
二叉搜索树	查找节点位置，插入，时间复杂度为log2(n),	找到根节点右子树最大的节点，时间复杂度为O（n）

如果在用二叉树结构

1. 删除的时候怎么设计？
2. 插入又应该怎么设计？

堆：完全二叉树结构

堆的结构定义

public class Heap {Integer[] data;int capacity;   //堆容量int size; //堆中元素个数int max=100000; public Heap(){this.capacity = 10;this.data = new Integer[capacity+1];//定义"哨兵"为大于堆中所有可能元素的值data[0] = max;}public Heap(int capacity) {this.data = new Integer[capacity+1];this.capacity = capacity;data[0] = max;}
}

2、最大堆的插入

1. 首先在堆尾部（数组的尾部）
2. 判断插入节点是否大于父节点，如果大于的话，插入节点和父节点互换位置，重复上述操作，直到出现插入节点小于父节点或者插入节点一路互换后变成根节点。

 public void insert(int value) {if (this.size==capacity) {this.data = (Integer[]) Arrays.copyOf(this.data, capacity * 2);}data[++size] = value;for (int i=size;i>0;i/=2) {if (data[i]>data[i/2]) {swap(data,i,i/2);	//数组中两数交换}}}

3、最大堆的删除

1. 首先保存要返回的根节点
2. 保存堆最后一个节点为X
3. 从根节点往下遍历，如果根节点的左右儿子有大于X的，那么左右儿子中大的值设置为根节点，将左右儿子中较大的节点作为该节点的儿子节点的根节点，重复上述判断。最后如果出现X大于根节点的左右儿子节点或者根节点为叶子节点时，将当前根节点设置为X。

 private Integer delete() {if (size==0){return null;} else {int parent,chrild = 0;int maxValue = data[1];int X = data[size--];for (parent = 1; parent<=size; parent = chrild) {chrild = parent*2;if (chrild!=size && (data[chrild]<data[chrild+1])) {chrild++;}if (X>data[chrild]) {break;} else {data[parent] = data[chrild];}}data[parent] = X;data[size+1] = null;return maxValue;}}

4、最大堆的建立

从堆最后一位的父节点开始，将该节点作为根节点，把该节点的堆调整为最大堆，然后依次取前一位父节点，直到根节点调整结束。

	public void createMaxHeap(int[] heap) {for ( int i=size/2; i>0;i/=2) {percDown(heap,i);}}private void percDown(int[] heap, int i) {int parent,chrild = 0;int X = data[i];for (parent = 1; parent<=size; parent = chrild) {chrild = parent*2;if (chrild!=size && (data[chrild]<data[chrild+1])) {chrild++;}if (X>data[chrild]) {break;} else {data[parent] = data[chrild];}}data[parent] = X;}