堆的基础表示
数据的存储规则
堆结构类似与二叉树（此处用最大堆举例），不同的是堆只用满足左右孩子均小于该节点值即可，由此，堆是一个完全二叉树（一层一层按顺序摆放数据）
用数组存储堆中的数据
由于堆中的数据存储方法满足完全二叉树（相当于顺序存储），故可以用数组顺序存储数据（从1开始）
由于后续删除、添加元素需要寻找节点的父亲节点、左孩子、右孩子，根据图示，易得出规律
MaxHeap基本方法的实现
public class MaxHeap <E extends Comparable<E>>{
private Array<E> data;
public MaxHeap(int capacity) {
data=new Array<>(capacity);
}
public MaxHeap() {
data=new Array<>();
}
//返回堆中元素的个数
public int size() {
return data.getSize();
}
//返回一个布尔值，表示堆是否为空
public boolean isEmpty() {
return data.isEmpty();
}
//返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
private int parent(int index) {
if(index==0)
throw new IllegalArgumentException("Index 0 doesn't have parent.");
return (index-1)/2;
}
//返回完全二叉树的数组表示中，一个索引所表示元素的左孩子节点
private int leftChild(int index) {
return index*2+1;
}
//返回完全二叉树的数组表示中，一个索引所表示元素的右孩子节点
private int rightChild(int index) {
return index*2+2;
}
}
向堆中添加元素
添加思路
首先在动态数组尾部添加元素
再向上寻找其父亲节点，比较父亲结点位置值，若该位置值大于父亲节点的值，间二者间的值进行交换，直至父亲结点值大于新添加的元素
代码实现
//向堆中添加元素
public void add(E e) {
data.addLast(e);
siftUp(data.getSize()-1);
}
private void siftUp(int k) {
while(k>0&&data.get(parent(k)).compareTo(data.get(k))<0) {//只有在k位置存在且值大于父亲节点的情况下才swap
data.swap(k, parent(k));
k=parent(k);
}
}
取出堆中的最大元素
取出最大元素很容易，问题就是如何对堆中其它元素进行操作
取出元素后，首先将数组末尾元素移到数组首部，填补空缺
再比较该结点与其孩子节点的值，选择大于该结点，且值较大的孩子结点进行交换
一直进行交换直至没有左右孩子或均大于左右孩子为止
代码实现
//取出堆中的最大元素
public E extractMax() {
E ret=findMax();
data.swap(0, data.getSize()-1);
data.removeLast();
siftDown(0);
return ret;
}
private void siftDown(int k) {
while(leftChild(k)<data.getSize()) {//循环条件为左孩子存在
int j=leftChild(k);
//首先判断右孩子是否存在，再比较两者的值，选择应该与谁交换
if(rightChild(k)<data.getSize()&&data.get(j).compareTo(data.get(j+1))<0)
j++;
if(data.get(k).compareTo(data.get(j))>=0)
break;
data.swap(k, j);
k=j;
}
}
将数组转换为堆
MaxHeap构造函数
想要将传入的数组原地转换为堆，方法很简单，只需找到倒数第一个非叶子节点，也就是最后一个节点的父亲节点（此处标为红色的位置），从此处依次往前，进行siftDown操作即可
MaxHeap中的heapify方法：
public MaxHeap(E[] arr) {
data=new Array<>(arr);
for(int i=parent(arr.length-1);i>=0;i--)
siftDown(i);
}
堆排序
堆排序
由于堆自身的特性，我们可以知道，索引为0的位置，永远存放堆中的最大元素。据此，我们可以利用堆对数组进行排序
public static <E extends Comparable<E>> void sort(E[] data) {
MaxHeap<E> maxHeap=new MaxHeap<>();
for(E e:data)
maxHeap.add(e);
for(int i=data.length-1;i>=0;i--) {
data[i]=maxHeap.extractMax();
}
}
优化的堆排序
想要对堆排序进行优化，我们可以对数组进行原地heapify，再对最大值进行处理
如图示，就是要原地实现数组的heapify,再将堆中第一个元素与最后一个元素交换位置。
- 交换位置后，堆可能不会满足最大堆的性质（图二中标黄的部分），所以要对第一个元素进行heapify，使其满足堆的性质。
- 接下来再重复这个操作
public static <E extends Comparable<E>> void sort2(E[] data) {
if(data.length<=1) return ;
//将普通数组转换为堆的形式
for(int i=(data.length-2)/2;i>=0;i--) {
siftDown(data,i,data.length);
//再对堆进行swap,siftDown操作
for(i=data.length-1;i>=0;i--) {
swap(data,0,i);
siftDown(data,0,i);
}
}
}
//对data[0,n)所形成的最大堆中，索引为k的元素，执行siftDown
private static <E extends Comparable<E>> void siftDown(E[] data,int k,int n) {
while(2*k+1<n) {//循环条件为左孩子存在
int j=2*k+1;
//首先判断右孩子是否存在，再比较两者的值，选择应该与谁交换
if(j+1<n&&data[j].compareTo(data[j+1])<0)
j++;
if(data[k].compareTo(data[j])>=0)
break;
swap(data,k, j);
k=j;
}
}
private static <E> void swap(E[] arr,int i,int j){
E tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}