二叉堆是一颗完全二叉树（除了最后一层其与节点的子节点都是最大值）
最大堆，结点越上，越大（二叉堆）
最小堆，节点越上，越大。
用数组存储二叉堆
shiftup
插入元素，先与i/2（父节点）比，如果父节点小，则调换位置，再与i/2/2（父亲的父亲）比，一直>0(跟节点)比，大于则交换位置。
shiftdown
从堆中取出一个元素，取出跟节点元素，将最后一个元素放到第一个元素的位置，数组容量-1，根节点和子节点比较，较大的与根节点调换位置，一直换下去，直到i=i*2>容量为止。
package bobo.algo;
import java.util.*;
import java.lang.*;
// 在堆的有关操作中，需要比较堆中元素的大小，所以Item需要extends Comparable
public class MaxHeap {
protected Item[] data;
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public MaxHeap(int capacity){
data = (Item[])new Comparable[capacity+1];
count =0;
this.capacity = capacity;
}
// 返回堆中的元素个数
public int size(){
return count;
}
// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty(){
return count ==0;
}
// 像最大堆中插入一个新的元素item
public void insert(Item item){
assert count +1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
// 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
public Item extractMax(){
assert count >0;
Item ret = data[1];
swap(1 , count );
count --;
shiftDown(1);
return ret;
}
// 获取最大堆中的堆顶元素
public Item getMax(){
assert( count >0 );
return data[1];
}
// 交换堆中索引为i和j的两个元素
private void swap(int i, int j){
Item t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* 最大堆核心辅助函数
//********************
private void shiftUp(int k){
while( k >1 && data[k/2].compareTo(data[k]) <0 ){
swap(k, k/2);
k /=2;
}
}
private void shiftDown(int k){
while(2*k <= count ){
int j =2*k; // 在此轮循环中,data[k]和data[j]交换位置
if( j+1 <= count && data[j+1].compareTo(data[j]) >0 )
j ++;
// data[j] 是 data[2*k]和data[2*k+1]中的最大值
if( data[k].compareTo(data[j]) >=0 )break;
swap(k, j);
k = j;
}
}
// 测试MaxHeap
public static void main(String[] args) {
MaxHeap maxHeap =new MaxHeap(100);
int N =100; // 堆中元素个数
int M =100; // 堆中元素取值范围[0, M)
for(int i =0 ; i < N; i ++ )
maxHeap.insert(new Integer((int)(Math.random() * M)) );
Integer[] arr =new Integer[N];
// 将maxheap中的数据逐渐使用extractMax取出来
// 取出来的顺序应该是按照从大到小的顺序取出来的
for(int i =0 ; i < N; i ++ ){
arr[i] = maxHeap.extractMax();
System.out.print(arr[i] +" ");
}
System.out.println();
// 确保arr数组是从大到小排列的
for(int i =1 ; i < N; i ++ )
assert arr[i-1] >= arr[i];
}
}
堆排序：
生成一个数组（大小+1），将原数组的每一个元素用insert插入，即完成了排序，再用extractMax();取出即可
public static void sort(Comparable[] arr){
int n = arr.length;
MaxHeap maxHeap =new MaxHeap(n);
for(int i =0 ; i < n; i ++ )
maxHeap.insert(arr[i]);
for(int i = n-1 ; i >=0 ; i -- )
arr[i] = maxHeap.extractMax();
}
堆排序的时间复杂度为nlogn
第二种堆排序算法
完全二叉树的第一个非叶子节点=节点数/2
将所有非叶子节点进行shiftdown即可
public MaxHeap(Item arr[]){
int n = arr.length;
data = (Item[])new Comparable[n+1];
capacity = n;
for(int i =0 ; i < n; i ++ )
data[i+1] = arr[i];
count = n;
for(int i = count/2 ; i >=1 ; i -- )
shiftDown(i);
}
public static void sort(Comparable[] arr){
int n = arr.length;
MaxHeap maxHeap =new MaxHeap(arr);
for(int i = n-1 ; i >=0 ; i -- )
arr[i] = maxHeap.extractMax();
}
这一种堆排序比上一种堆排序更快一点，但是堆排序还是比归并排序要慢。
如果交换的时间耗时过长可以使用索引堆，只是交换索引即可
网友评论