堆排序
堆(Heap)：(维基百科)
堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。
二叉堆需要满足的性质：
1、堆上任何一个节点都不大于它的父亲节点（最大堆）
2、堆是一颗完全的二叉树(即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入)
对于堆中的任何节点i：
- 其父节点索引为
parent(i) = i/2 - 其左孩子节点索引为
left child (i) = 2 * i - 其又孩子节点索引为
right child (i) = 2 * i + 1
最大堆的数据结构
public class MaxHeap<Item> {
private Item[] data;
private int count;
public MaxHeap(int capacity) {
data = (Item[]) new Object[capacity];
count = 0;
}
public int size() {
return count;
}
public boolean isEmpty() {
return count == 0;
}
}
Shift Up
插入一个节点，需要维护二叉堆的性质：
public class MaxHeap<Item extends Comparable> {
private Item[] data;
private int count;
private int 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;
}
public void insert(Item item) {
assert (count < capacity);
data[count + 1] = item;
count++;
shiftUp(count);
}
private void shiftUp(int k) {
while (k > 1 && data[k].compareTo(data[k / 2]) < 0) {
swap(data, k, k / 2);
k /= 2;
}
}
private void swap(Item[] data, int k, int i) {
Item temp = data[k];
data[k] = data[i];
data[i] = temp;
}
}
ShiftDown
// 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
public Item extractMax() {
assert count > 0;
Item ret = data[1];
swap(1, count);
count--;
shiftDown(1);
return ret;
}
private void shiftDown(int k) {
while ( 2 * k <= count) { // 如果有左孩子
int j = 2 * k; // 在此轮循环中,data[k]和data[j]交换位置
if (j+1 <= count && data[j].compareTo(data[j + 1]) < 0) {
j++; // data[j] 是 data[2*k]和data[2*k+1]中的最大值
}
if (data[k].compareTo(data[j]) >= 0) {
break;
}
swap(k,j);
k = j;
}
}
Heapify
构造函数, 通过一个给定数组创建一个最大堆
// 该构造堆的过程, 时间复杂度为O(n)
public MaxHeap(Item[] arr) {
int n = arr.length;
data = (Item[]) new Comparable[n + 1];
for (int i = 0; i < n; i++) {
data[i + 1] = arr[i];
}
count = n;
for (int i = count / 2; i >= 1; i--) {
shiftDown(i);
}
}
Heapify的算法复杂度
将n个元素逐个插入到一个空堆中，算法复杂度是O(nlogn) heapify的过程，算法复杂度为O(n)
堆排序实现1
对整个arr数组使用HeapSort1排序,HeapSort1, 将所有的元素依次添加到堆中, 在将所有元素从堆中依次取出来, 即完成了排序,无论是创建堆的过程, 还是从堆中依次取出元素的过程, 时间复杂度均为O(nlogn),整个堆排序的整体时间复杂度为O(nlogn)
public static void sort(Comparable[] arr){
int n = arr.length;
MaxHeap<Comparable> maxHeap = new MaxHeap<Comparable>(n);
for( int i = 0 ; i < n ; i ++ )
maxHeap.insert(arr[i]);
for( int i = n-1 ; i >= 0 ; i -- )
arr[i] = maxHeap.extractMax();
}
堆排序实现2
对整个arr数组使用HeapSort2排序,HeapSort2,借助我们的heapify过程创建堆,此时, 创建堆的过程时间复杂度为O(n), 将所有元素依次从堆中取出来, 实践复杂度为O(nlogn),堆排序的总体时间复杂度依然是O(nlogn), 但是比HeapSort1性能更优, 因为创建堆的性能更优
public static void sort(Comparable[] arr){
int n = arr.length;
MaxHeap<Comparable> maxHeap = new MaxHeap<Comparable>(arr);
for( int i = n-1 ; i >= 0 ; i -- )
arr[i] = maxHeap.extractMax();
}
原地堆排序
将最左边的max不断的移动到最右边
如果最大堆从索引0开始排序：
索引堆(Index Heap)
最大索引堆的实现
package bobo.algo;
import java.util.*;
import java.lang.*;
// 最大索引堆
public class IndexMaxHeap<Item extends Comparable> {
protected Item[] data; // 最大索引堆中的数据
protected int[] indexes; // 最大索引堆中的索引
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public IndexMaxHeap(int capacity){
data = (Item[])new Comparable[capacity+1];
indexes = new int[capacity+1];
count = 0;
this.capacity = capacity;
}
// 返回索引堆中的元素个数
public int size(){
return count;
}
// 返回一个布尔值, 表示索引堆中是否为空
public boolean isEmpty(){
return count == 0;
}
// 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
public void insert(int i, Item item){
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i += 1;
data[i] = item;
indexes[count+1] = i;
count ++;
shiftUp(count);
}
// 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
public Item extractMax(){
assert count > 0;
Item ret = data[indexes[1]];
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
// 从最大索引堆中取出堆顶元素的索引
public int extractMaxIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
// 获取最大索引堆中的堆顶元素
public Item getMax(){
assert count > 0;
return data[indexes[1]];
}
// 获取最大索引堆中的堆顶元素的索引
public int getMaxIndex(){
assert count > 0;
return indexes[1]-1;
}
// 获取最大索引堆中索引为i的元素
public Item getItem( int i ){
assert i + 1 >= 1 && i + 1 <= capacity;
return data[i+1];
}
// 将最大索引堆中索引为i的元素修改为newItem
public void change( int i , Item newItem ){
i += 1;
data[i] = newItem;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后shiftUp(j), 再shiftDown(j)
for( int j = 1 ; j <= count ; j ++ )
if( indexes[j] == i ){
shiftUp(j);
shiftDown(j);
return;
}
}
// 交换索引堆中的索引i和j
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
}
//********************
//* 最大索引堆核心辅助函数
//********************
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k;
if( j+1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) > 0 )
j ++;
if( data[indexes[k]].compareTo(data[indexes[j]]) >= 0 )
break;
swapIndexes(k, j);
k = j;
}
}
// 测试索引堆中的索引数组index
// 注意:这个测试在向堆中插入元素以后, 不进行extract操作有效
public boolean testIndexes(){
int[] copyIndexes = new int[count+1];
for( int i = 0 ; i <= count ; i ++ )
copyIndexes[i] = indexes[i];
copyIndexes[0] = 0;
Arrays.sort(copyIndexes);
// 在对索引堆中的索引进行排序后, 应该正好是1...count这count个索引
boolean res = true;
for( int i = 1 ; i <= count ; i ++ )
if( copyIndexes[i-1] + 1 != copyIndexes[i] ){
res = false;
break;
}
if( !res ){
System.out.println("Error!");
return false;
}
return true;
}
// 测试 IndexMaxHeap
public static void main(String[] args) {
int N = 1000000;
IndexMaxHeap<Integer> indexMaxHeap = new IndexMaxHeap<Integer>(N);
for( int i = 0 ; i < N ; i ++ )
indexMaxHeap.insert( i , (int)(Math.random()*N) );
assert indexMaxHeap.testIndexes();
}
}
上面的代码change的复杂度O(n)还可以优化：