定义:
- 堆是一颗完全二叉树;
- 堆中的某个结点的值总是大于等于(最大堆)或小于等于(最小堆)其孩子结点的值。
- 堆中每个结点的子树都是堆树。
数据结构:
C 语言
struct MaxHeap
{
EType *heap; //存放数据的空间,下标从1开始存储数据,下标为0的作为工作空间,存储临时数据。
int MaxSize; //MaxSize是存放数据元素空间的大小
int HeapSize; //HeapSize是数据元素的个数
};
MaxHeap H;
初始化堆
public static void MaxHeapInit(int[] array) {
for(int i = array.length/2; i > 0; --i){
array[0] = array[i];//堆值存储从1开始,使用array[0]暂存
int child = 2*i;
while(child < array.length){
if (child < array.length - 1 && array[child] < array[child+1])
child++;
if(array[0] > array[child])
break;
array[child/2] = array[child];
child = child*2;
}
array[child/2] = array[0];
}
}
最大堆中插入结点
- 最大堆中插入节点,先在堆末尾插入该节点,然后按照堆的初始化过程将该节点放入到合适的位置。
C 语言源码
void MaxHeapInsert(MaxHeap &H, EType &x)
{
if(H.HeapSize==H.MaxSize) return false;
int i=++H.HeapSize;
while(i!=1&&x>H.heap[i/2]){
H.heap[i]=H.heap[i/2];
i/=2;
}
H.heap[i]=x;
return true;
}
最大堆中删除结点
- 将最大堆的最后一个节点放到根节点,然后删除最大值,然后再把新的根节点放到合适的位置
实战:
- 堆排序的基本思想:
利用大顶堆(或者小顶堆也行),将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是使其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次大值。如此反复执行,便能得到一个有序序列了。
升序排序使用大顶堆,降序排序使小顶堆;
public class Main {
public static void main(String[] args) {
int[] array = { 0, 20, 70, 30, 10, 60, 50, 30, 90, 100 };
String aString = Arrays.toString(array);
System.out.println("排序前 " + aString);
heapSort(array);
aString = Arrays.toString(array);
System.out.println("排序后 " + aString);
}
public static void heapSort(int[] array) {
for (int i = array.length / 2; i > 0; i--) { // 建堆
heapAdjust(array, i, array.length - 1);
}
for (int i = array.length - 1; i > 1; i--) {
swap(array, 1, i); //将最大值交换到最后
heapAdjust(array, 1, i - 1);//将剩余数组更新堆
}
}
public static void heapAdjust(int[] array, int small, int large) {
int temp = array[small];
for (int j = small * 2; j <= large; j = j * 2) {
if (j < large && array[j] < array[j + 1]) {
j++;
}
if (temp >= array[j])
break;
array[small] = array[j];
small = j;
}
array[small] = temp;
}
public static void swap(int[] array, int small, int large) {
int temp = array[small];
array[small] = array[large];
array[large] = temp;
}
}
网友评论