if ( R[i].key > R[j].key ) { R[i] <－> R[j] ; // 将较小的孩子与根交换 － i = j ; j = 2*i ; // 上述交换可能使以该孩子结点为根的
子树不再为堆， 子树不再为堆，则需重新调整
} else break ; } }
将初始无序的R[1]到R[n]建成一个小根堆，可用以 到 建成一个小根堆， 将初始无序的 建成一个小根堆 下语句实现： 下语句实现： for ( i = n/2 ; i >= 1 ; i - - ) sift ( R , i , n ) ;
Heapsort
Fig. 27-9 A trace of heapsort (g – i)
Heapsort
时间复杂度分析
该方法创建堆的时间复杂度为O( n ) 证明过程请看教材341页
7.5.2 堆和堆排序
一、堆和堆排序的概念 二、堆的调整 三、建堆 ☞ 四、堆排序
Heapsort
Fig. 27-9 A trace of heapsort (a – c)
Heapsort
Fig. 27-9 A trace of heapsort (d – f)
{ int j ; j = 2*i ; while ( j <= m)
//若j<=m，R[2*i]是R[i]的左孩子 若 ， 是 的左孩子
{ if ( j<m &&R[j].key> R[j+1].key)
比较左右孩子的大小， 为较小的孩子的下标 j ++ ; // 比较左右孩子的大小，使j为较小的孩子的下标
由于堆实质上是一个完全二叉树，那么我们可以 顺序存储一个堆。 顺序存储一个堆 下面以一个实例介绍建一个小根堆的过程。 例：有关键字为49，38，65，97，76，13，27， 例： 49的一组记录，将其按关键字调整为一个小根堆。
49 38 97 49 76 13 65 27
13 49 38 97 49 97 49 76 13 65 27 13 49 65
你能画出删除堆顶元素时相应数组的变化吗？ 你能画出删除堆顶元素时相应数组的变化吗？ 删除元素代码见课本204 删除元素代码见课本7.Fra bibliotek.2 堆和堆排序
一、堆和堆排序的概念 二、堆的调整 ☞ 三、建堆 四、堆排序
第一种方法：
把一个数组看成两部分，左边是堆，右边是还 没加入堆的元素，步骤如下： 1、数组里的第一个元素自然地是一个堆 2、然后从第二个元素开始，一个个地加入左 边的堆，当然，每加入一个元素就破坏了左边 元素堆的性质，得重新把它调整为堆
4 15 16 25 7 5 12 11 8 9
6 23 27 20
Example (end)
10 4 15 16 25 7 5 12 11 8 9 27 6 23 20
4 5 15 16 25 10 7 12 11 8 9 27 6 23 20
Analysis
We visualize the worst-case time of a downheap with a proxy path that goes first right and then repeatedly goes left until the bottom of the heap (this path may differ from the actual downheap path) Since each node is traversed by at most two proxy paths, the total number of nodes of the proxy paths is O(n) Thus, bottom-up heap construction runs in O(n) time Bottom-up heap construction is faster than n successive insertions and speeds up the first phase of heap-sort
删除元素
Fig. 27-5 The steps to remove the entry in the root of the maxheap of Fig. 27-3d
Removing the Root
Fig. 27-6 The steps that transform a semiheap into a heap without swaps.
Adding an Entry
Begin at next available position for a leaf Follow path from this leaf toward root until find correct position for new entry As this is done
Adding an Entry----代码见课本203
Algorithm for adding new entry to a heap
Algorithm add(newEntry) if (the array heap is full) Double the size of the array newIndex = index of next available array location parentIndex = newIndex/2 // index of parent of available location while (newEntry > heap[parentIndex]) { heap[newIndex] = heap[parentIndex] // move parent to available location // update indices newIndex = parentIndex parentIndex = newIndex/2 } // end while
6 7 8
0
1
2
3
4
5
49 65 13 27 97 13 38 27 49 76 65 49 49 49 13 97
筛选过程的算法描述为： sift (rectype R[ ] , int i , int m )
// 在数组 中将下标从 到m的元素序列调整为堆，即将以 在数组R中将下标从 中将下标从i到 的元素序列调整为堆 的元素序列调整为堆， R[i]为根的子树调整为堆；初次调整的是以序号 为根的子树调整为堆； 为根的子树调整为堆 初次调整的是以序号m/2的结点为根的 的结点为根的 子树； 子树；
自底向上地创建堆
16
15
4
12
6
7
23
20
25 16 15 4
5 12 6
11 7 23
27 20
Example (contd.)
25 16 15 4
5 12 6
11 9 23
27 20
15 16 25 5
4 12 11
6 9 27
23 20
Example (contd.)
7 15 16 25 5 4 12 11 6 9 27 8 23 20
Move entries from parent to child Makes room for new entry
Adding an Entry
Fig. 27-3 A revision of steps shown in Fig. 27-2 to avoid swaps.
Adding an Entry
堆与堆排序
软件学院 王建文
7.5.2 堆和堆排序
☞ 一、堆和堆排序的概念 二、堆的调整 三、建堆 四、堆排序
堆的定义： 个元素的序列{a 若n个元素的序列 1 a2 … an} 满足 个元素的序列 ai ≤ a2i ai ≤ a2i+1 或 ai ≥ a2i ai ≥ a2i+1
则分别称该序列{a 大根堆。 则分别称该序列 1 a2 … an}为小根堆 和大根堆。 为 从堆的定义可以看出， 从堆的定义可以看出，堆实质是满足如下性质的完 全二叉树： 全二叉树： 二叉树中任一非叶子结点均小于(大于) 二叉树中任一非叶子结点均小于(大于)它的孩子结点
Fig. 27-4 An array representation of the steps in Fig. 27-3 … continued →
Adding an Entry
Fig. 27-4 (ctd.) An array representation of the steps in Fig. 27-3.
堆排序 若在输出堆顶的最小值（最大值） 若在输出堆顶的最小值（最大值）后，使得剩余 n-1个元素的序列重又建成一个堆，则得到n个元素 个元素的序列重又建成一个堆，则得到 个元素 个元素的序列重又建成一个堆 的次小值（次大值） 如此反复， 的次小值（次大值）……如此反复，便能得到一个 如此反复 有序序列，这个过程称之为堆排序 堆排序。 有序序列，这个过程称之为堆排序。
首先， 调整从第n/2 n/2个元素开始 首先， 调整从第n/2个元素开始 将以该元素为根的二叉树调整为堆 然后，将以序号为n/2 n/2－ 然后，将以序号为n/2－1的结点 为根的二叉树调整为堆； 为根的二叉树调整为堆； 27 49 再将以序号为n/2 n/2－ 再将以序号为n/2－2的结点为根 的二叉树调整为堆； 的二叉树调整为堆； 再将以序号为n/2 n/2－ 再将以序号为n/2－3的结点为根 的二叉树调整为堆； 的二叉树调整为堆；
显然： 单结点的二叉树是堆； 单结点的二叉树是堆；在完全二叉树中所有以叶子 结点（序号i 结点（序号 > n/2）为根的子树是堆。 ）为根的子树是堆。 这样，我们只需依次将以序号为 ， － ， 这样，我们只需依次将以序号为n/2，n/2－1，……, 1的结点为根的子树均调整为堆即可。 的结点为根的子树均调整为堆即可。 的结点为根的子树均调整为堆即可 即：对应由n个元素组成的无序序列，“筛选” 即：对应由n个元素组成的无序序列，“筛选”只需 从第n/2个元素开始。 从第n/2个元素开始。