堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树
堆支持的操作：
- build:建立一个空堆；
- insert:向堆中插入一个新元素；
- update：将新元素提升使其符合堆的性质；
- get：获取当前堆顶元素的值；
- delete：删除堆顶元素；
- heapify：使删除堆顶元素的堆再次成为堆。
而堆排序则是利用堆的数据结构而设计的一种排序算法。
插入操作
插入操作也叫做shiftUp即向上移动的过程，步骤如下：
- 像堆的最后一个位置插入一个元素，记录数组下标
- 判断最后新插入的元素是否大于其父节点的元素
- 如果大于其父节点的元素，与父元素交换位置，继续第2步操作，直到当前元素小于父节点元素的值。
// 像最大堆中插入一个新的元素 item
public void insert(Item item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
private void shiftUp(int count){
while(count > 1 && data[count / 2 ] < data[count]){
swap(count,count/2);
count = count / 2;
}
}移除最大元素
流程：
- 移除数组第一个元素，(堆存储中第一个元素的下标为1)
- 将数组中最后一个元素放入第一个元素。
- 从第一个元素向下比较, 假设当前元素为k, 其子元素的下标则是(2k+1)与2k。
- 如果当前元素小于其子元素中的某一个，与子元素中较大的那个交换位置。继续第2步操作。
- 直到当前元素大于其两个子元素
实现：
/*
take out A[1]
A[1] = A[A.length-1]
i = 1; A.length--
while (i < A.length)
if A[i] < (L = the larger of i's children)
swap(A[i], L)
*/
private int extractMax(){
assert count >= 0;
int retVal = data[1];
data[1] = data[count];
count--;
shiftDown(1);
return retVal;
}
private void shiftDown(int j) {
while (2 * j <= count){
int k = 2 * j;
// 注意子节点的边界，可能只有右子节点
if (k + 1 <= count && data[k] < data[k+1]){
k = k + 1;
}
if (data[j] > data[k]) {
break;
}
swap(j,k);
j = k;
}
}堆排序
既然可以做到了每次都移除最大的元素，那么排序就简单了。
流程：(对数组排序)
方式1： 数组的堆化
利用循环，每次进行插入操作
for( i=0;i < arr.length;i ++ ){
insert(i);
}方式2：直接对数组赋值，然后不断的进行shiftdown操作
public HeapSort(int[] arr){
data = new int[arr.length + 1];
capcity = arr.length;
for (int i = 0; i < arr.length; i++) {
data[i + 1] = arr[i];
}
count = arr.length;
for (int i = count / 2 ; i >= 1; i--) {
shiftDown(i);
}
}完整代码
将堆定义成一个对象来操作。
public class HeapSort {
private int[] data;
/**
* 堆元素能存储的个数
*/
private int capcity;
/**
* 堆元素的个数
*/
private int count;
public HeapSort(int capcity) {
this.capcity = capcity;
this.count = 0;
this.data = new int[capcity + 1];
}
public void insert(int i){
if (count > capcity){
//
return;
}
data[count + 1] = i;
count++;
shiftUp(count);
}
private void shiftUp(int count) {
// 0010
int pNodeIndex = count >> 1;
while (data[count] > data[pNodeIndex] && pNodeIndex > 0){
swap(count,pNodeIndex);
count = pNodeIndex;
pNodeIndex = count >> 1;
}
}
private void swap(int count, int pNodeIndex) {
int tmp = data[count];
data[count] = data[pNodeIndex];
data[pNodeIndex] = tmp;
}
private int extractMax(){
assert count >= 0;
int retVal = data[1];
data[1] = data[count];
count--;
shiftDown(1);
return retVal;
}
private void shiftDown(int j) {
//拿走第一个元素，把其他元素进行重新建堆
//与子元素比较，与更大的一个子元素交换位置。
while (2 * j <= count){
int k = 2 * j;
if (k + 1 <= count && data[k] < data[k+1]){
k = k + 1;
}
if (data[j] > data[k]) {
break;
}
swap(j,k);
j = k;
}
}
//将一个数组进行堆化的过程
public HeapSort(int[] arr){
data = new int[arr.length + 1];
capcity = arr.length;
for (int i = 0; i < arr.length; i++) {
data[i + 1] = arr[i];
}
count = arr.length;
for (int i = count / 2 ; i >= 1; i--) {
shiftDown(i);
}
}
public int size(){
return count;
}
public static void main(String[] args) {
// HeapSort heapSort = new HeapSort(10);
int[] a = new int[10];
for (int i = 0; i < 10; i++) {
a[i] = i;
}
HeapSort sort = new HeapSort(a);
int size = sort.size();
for (int i = 0; i < size; i++) {
System.out.println(sort.extractMax());
}
}
}
最后
写算法的时候注意边界问题，多写几遍才能理解的更深刻。