【数据结构】堆，堆的建立，插入以及删除（以大堆为例）
目录
1.堆的性质：
2.堆的存储方式
2.1大堆和小堆存储示意图
3.堆的创建（以大堆为例）
1.创建一个线性表用来存放数据
2.堆的插入
图解：
3.堆的删除
图解：
1.堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树
2.堆的存储方式
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，
2.1大堆和小堆存储示意图
3.堆的创建（以大堆为例）
1.创建一个线性表用来存放数据
public class MaxHeap {//存放元素的数组private List<Integer> data;//有效元素个数private int size;public MaxHeap(){this(3);}public MaxHeap(int capacity) {this.data = new ArrayList<>(capacity);}
}2.堆的插入
1.先将元素插入到堆的末尾，即最后一个孩子之后
2.插入之后如果堆的性质遭到破坏，将新插入的节点顺着双亲往上调整到合适的位置即可
图解：
// 向最大堆中添加元素public void add(int val){//尾插data.add(val);size++;//元素上浮siftUp(size - 1);}private void siftUp(int k) {while(k > 0 && data.get(k) > data.get(parent(k))){swap(k,parent(k));k = parent(k);}}private void swap(int i, int j){int temp = data.get(i);data.set(i,data.get(j));data.set(j,temp);}
3.堆的删除
堆的删除一定删除的是堆顶元素，具体如下：
1.将对顶元素与最后一个元素交换
2.将堆中有效元素个数减少一个
3.对堆顶元素向下调整
图解：
//删除最大元素public int delete(){//头尾元素交换，size--int val = data.get(0);data.set(0,data.get(this.size - 1));size--;//元素下沉shiftDown(0);data.remove(size);return val;}private void shiftDown(int k) {while (rightChild(k) <= size && (data.get(k) < data.get(leftChild(k)) ||data.get(k) < data.get(rightChild(k)))) {//判断左右子树谁大if (data.get(leftChild(k)) > data.get(rightChild(k))) {swap(k, leftChild(k));k = leftChild(k);} else {swap(k, rightChild(k));k = rightChild(k);}}}private void swap(int i, int j){int temp = data.get(i);data.set(i,data.get(j));data.set(j,temp);}