Tianlong'S
0%

堆排序(一)

发表于 分类于

堆定义

从简单的二叉堆定义：在二叉堆的数组中，每个元素都要保证大于等于另外两个特定位置的元素。这些位置的元素又至少大于等于数组中的另外两个元素。

在堆有序的二叉树中，每个结点都要小于等于它的父结点，从任意结点向上，我们都能得到一列非递减的元素；从任意结点向下，我们都能得到一列非递增的元素。

如果用数组表示的话，在一个堆中，位置为k的结点的父亲结点位置为k/2,而它的两个子结点位置分别为2k和2k+1。

同样由二叉堆启发，我们可以构造出三叉堆，乃至多叉堆。

堆的算法

堆底插入元素时，要由下至上恢复堆的顺序,堆上浮
1
2
3
4
5
6
private void swim(int k) {
	while(k > 1 && less(k/2, k)) {
    	exch(k/2, k);
        k = k/2;
    }
}
某结点替换为一个元素，需要由上至下恢复堆，堆下沉
1
2
3
4
5
6
7
8
9
private void sink(int k) {
	while(2*k < n) {
    	int j = 2*k;
        if (j < n && less(j, j+1)) j++;
        if (!less(k, j)) break;
        exch(k,j);
        k = j;
    }
}
构造堆，堆下沉法（也可以用扫描所有元素来进行堆上浮）
1
2
3
4
5
6
public static void make(Comparable[] a) {
	int N = a.length;
    for(int k=N/2; k>=1, k--) {
    	sink(a, k ,N);
    }
}
堆排序
1
2
3
4
5
6
7
8
9
10
11
public static void make(Comparable[] a) {
	int N = a.length;
    for(int k=N/2; k>=1, k--) {
    	sink(a, k ,N);
    }
    
    while(N > 1) {
    	exch(a, 1, N--);//最大元素和最后一个元素兑换
        sink(a, 1, N);//调整堆顺序，根结点最大
    }
}
应用
  • 实现基于堆的优先队列
  • 堆排序