数据结构之堆
堆
堆是一种特殊的数据结构，通常可以看作是一颗完全二叉树的数组对象。
堆的特性
它是完全二叉树，除树的最后一层节点不需要是满的，其他的每一层从左到右都是满的，如果最后一层不是满的，则要求左满右不满。
它通常使用数组来实现
具体方法是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子节点的子结点分别在位置4、5、6和7，以此类推。
如果一个结点的位置是k，则它父节点的位置为[k/2]，而它两个子结点的位置分别为2k和2k+1。
每个结点都大于它的两个子结点
堆的API设计
堆的实现
insert插入方法的实现
堆插入元素图解（上浮算法）：
所以，如果往堆中新插入元素，我们只需要不断的比较新结点a[k]和它父节点a[k/2]的大小，然后根据结果完成数据元素的交换，就可以完成堆的有序调整。
删除方法的实现
删除堆元素图解（下沉算法）：
所以，当删除掉最大元素后，只需要将最后一个元素放到索引1处，并不断拿着当前节点a[k]和它的子结点a[2k]和a[2k+1]中的较大者交换位置，即可完成堆的有序调整。
堆的代码实现
public class Heap<T extends Comparable<T>> {private T[] items;/*** 堆大小，索引0处不存元素，从索引1开始*/private int size;/*** 构造函数** @param capacity*/public Heap(int capacity) {items = (T[]) new Comparable[capacity + 1];size = 0;}/*** 向堆中插入一个元素** @param item*/public void insert(T item) {//向数组添加一个元素items[++size] = item;//使用上浮算法，使得元素处于一个正确位置swim(size);}/*** 删除堆中最大元素** @return*/public T delMax() {//根据堆的特性，堆中最大的值是根结点的值T max = items[1];//先将堆中最后一个结点和根结点交换位置exch(1,size);//将最后一个结点置为null，元素个数-1items[size--] = null;//使用下沉算法使得更新后的根结点处在正确的位置sink(1);return max;}/*** 使用上浮算法，使得索引k处的值处于一个正确的位置* @param k*/private void swim(int k){while (k > 1){if(less(k/2,k)){exch(k/2,k);k = k/2;}else {break;}}}/*** 使用下沉算法，使得索引k处的值处于一个正确的位置* @param k*/private void sink(int k){while (2*k <= size){//找到两个子结点较大的那个的索引int max = 2*k;if(2*k+1 < size){if(less(2*k,2*k+1)){max = 2*k + 1;}}//比较当前索引处的值和较大结点处的值，如果当前索引处的值小于较大结点处的值，则交换两处的值if(!less(k,max)){break;}exch(k,max);k = max;}}/*** 比较索引i处和索引j处的值大小，i处小于j处则返回true** @param i* @param j* @return*/private boolean less(int i, int j) {return items[i].compareTo(items[j]) < 0;}private void exch(int i, int j) {T temp = items[i];items[i] = items[j];items[j] = temp;}public String toString() {return "Heap{" +"items=" + Arrays.toString(items) +", size=" + size +'}';}}//测试代码public class HeapTest {public static void main(String[] args) {Heapheap = new Heap<>(6); heap.insert("C");heap.insert("B");heap.insert("A");heap.insert("D");heap.insert("F");heap.insert("E");System.out.println(heap);String result;while ((result=heap.delMax()) != null){System.out.println(result);}}}
堆排序
给定一个数组：
String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};请对数组中的字符从小到大排序。
API设计：
类名
HeapSort
成员方法
//对source数组进行从小到大排序
public static void sort(Comparable[] source);
//根据原数组创建heap堆
private static void createHeap(Comparable[] source,Comparable[] heap);
//比较堆中索引i处和索引j处的值，小于返回true
private static boolean less(Comparable[] heap,int i,int j);
//交换heap堆中i索引和j索引处的值
private static void exchange(Comparable[] heap,int i,int j);
//在堆中，对target处的元素进行下沉，范围0-range
private static void sink(Comparable[] heap,int target,int range);
实现步骤
构造堆heap
将原数组复制给一个新数组
对数组中元素进行下沉，让它有序，符合堆的定义
根据堆的特性，根结点的值最大，交换根结点和最大索引处的值，将堆分为两部分，未排序的数组（0-length-2），和已排序的数组（length-1）然后对根节点在未排序数组中进行下沉
继续执行步骤2，直到最后一个元素
将堆heap的元素复制给原数组
代码实现
public class HeapSort<T extends Comparable<T>> {
//对source数组进行从小到大排序
public static void sort(Comparable[] source) {
Comparable[] heap = new Comparable[source.length+1];
createHeap(source,heap);
//记录未排序最大索引
int N = heap.length -1;
while (N!=1){
//交换根结点和最后一个未排序索引处的值
exchange(heap,1,N);
N--;
//对交换过的根结点进行下沉，范围除去已排序的索引
sink(heap,1,N);
}
//把heap中的数据复制回source数组
System.arraycopy(heap,1,source,0,source.length);
}
//根据原数组创建heap堆
private static void createHeap(Comparable[] source, Comparable[] heap) {
//复制原数组到heap
System.arraycopy(source,0,heap,1,source.length);
//对堆中的元素进行下沉，（从长度一半开始，往1处扫描）
for (int i = heap.length/2; i > 0; i--) {
sink(heap,i, heap.length-1);
}
}
//比较堆中索引i处和索引j处的值，小于返回true
private static boolean less(Comparable[] heap, int i, int j) {
return heap[i].compareTo(heap[j]) < 0;
}
//交换heap堆中i索引和j索引处的值
private static void exchange(Comparable[] heap, int i, int j) {
Comparable temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
//在堆中，对target处的元素进行下沉，范围0-range
private static void sink(Comparable[] heap, int target, int range) {
while (2*target <= range){
//找出当前结点较大子结点
int max = 2*target;
if(2*target+1 <= range){
if (less(heap,2*target,2*target+1)){
max = 2*target+1;
}
}
//比较当前结点和较大子结点的值
if (!less(heap, target, max)){
break;
}
exchange(heap,target,max);
target = max;
}
}
}
思考：
上面实现的也叫最大堆，堆中第一个元素总是最大的，还有一种堆叫最小堆，即堆中第一个元素总是最小的，又应该如何实现？
上面的实现都是固定容量大小的，如果需要实现可变容量又应该如何实现？
你知道的越多，不知道的就越多，关注我，我们一起进步。如果觉得文章还可以，请给帮我点个赞，谢谢~我们下期见。
评论