堆排序算法详解堆排序算法|算法设计与分析

本文概述

二进制堆
堆属性
堆砌方法
建立一个堆
堆排序算法
优先队列
最大堆（A）
堆删除

二进制堆 Binary Heap是一个数组对象, 可以视为Complete Binary Tree。二叉树的每个节点对应于数组中的一个元素。

长度[A], 数组中的元素数
Heap-Size [A], 数组A中存储的堆中的元素数。

树A [1]的根, 给出节点的索引“ i”, 该节点可以计算其父节点, 左子节点和右子节点的索引。

PARENT (i) Return floor (i/2)LEFT (i) Return 2iRIGHT (i) Return 2i+1

文章图片
上图的数组表示如下：

文章图片
索引20为1
为了找到左孩子的索引, 我们计算1 * 2 = 2
这使我们（正确地）到达了14。
现在, 我们往右走, 所以我们计算2 * 2 + 1 = 5
这将我们（正确地）带到了6。
现在, 4的索引是7, 我们想转到父级, 所以我们计算7/2 = 3, 这使我们到了17。
堆属性二进制堆可以分为最大堆或最小堆
1.最大堆：在二进制堆中, 对于除根以外的每个节点I, 该节点的值都大于或等于其最高子节点的值

A [PARENT (i) ≥A[i]

因此, 堆中的最高元素存储在根目录中。以下是MAX-HEAP的示例

文章图片
2. MIN-HEAP：在MIN-HEAP中, 节点的值小于或等于其最低子节点的值。

A [PARENT (i) ≤A[i]

文章图片
堆砌方法 1.维护堆属性：堆化是用于操纵堆数据结构的过程。给它一个数组A, 并给数组下标I。以A [i]的子节点为根的子树是堆, 但是节点A [i]本身可能会违反堆属性, 即A [i] < A [2i]或A [2i + 1]。 “堆化”过程操作以A [i]为根的树, 使其成为堆。

MAX-HEAPIFY (A, i) 1. l ← left [i] 2. r ← right [i] 3. if l≤ heap-size [A] and A[l] > A [i] 4. then largest ← l 5. Else largest ← i 6. If r≤ heap-size [A] and A [r] > A[largest] 7. Then largest ← r 8. If largest ≠ i 9. Then exchange A [i]A [largest] 10. MAX-HEAPIFY (A, largest)

分析：
元素可以向上移动的最大电平为Θ（log n）电平。在每个级别上, 我们都对O（1）进行简单比较。因此, heapify的总时间为O（log n）。
建立一个堆

BUILDHEAP (array A, int n) 1 for i ← n/2 down to 1 2 do 3 HEAPIFY (A, i, n)

堆排序算法

HEAP-SORT (A) 1. BUILD-MAX-HEAP (A) 2. For I ← length[A] down to Z 3. Do exchange A [1] ←→ A [i] 4. Heap-size [A] ← heap-size [A]-1 5. MAX-HEAPIFY (A, 1)

分析：构建最大堆需要O（n）运行时间。堆排序算法调用“ Build Max-Heap”（构建最大堆）, 这需要O（n）个时间, 而每个（n-1）个调用都将调用Max-heap来修复新堆。我们知道“ Max-Heapify”需要时间O（log n）
堆排序的总运行时间为O（n log n）。
示例：说明阵列上BUILD-MAX-HEAP的操作。

A = (5, 3, 17, 10, 84, 19, 6, 22, 9)

解决方案：最初：

Heap-Size (A) =9, so first we call MAX-HEAPIFY (A, 4)And I = 4.5= 4 to 1

文章图片

After MAX-HEAPIFY (A, 4) and i=4 L ← 8, r ← 9 l≤ heap-size[A] and A [l] > A [i] 8 ≤9 and 22> 10 Then Largest ← 8 If r≤ heap-size [A] and A [r] > A [largest]9≤9 and 9> 22 If largest (8) ≠4 Then exchange A [4] ←→ A [8] MAX-HEAPIFY (A, 8)

文章图片

After MAX-HEAPIFY (A, 3) and i=3l← 6, r ← 7l≤ heap-size[A] and A [l] > A [i]6≤ 9 and 19> 17Largest ← 6If r≤ heap-size [A] and A [r] > A [largest]7≤9 and 6> 19If largest (6) ≠3Then Exchange A [3] ←→ A [6]MAX-HEAPIFY (A, 6)

文章图片

After MAX-HEAPIFY (A, 2) and i=2l ← 4, r ← 5l≤ heap-size[A] and A [l] > A [i]4≤9 and 22> 3Largest ← 4If r≤ heap-size [A] and A [r] > A [largest]5≤9 and 84> 22Largest ← 5If largest (4) ≠2Then Exchange A [2] ←→ A [5]MAX-HEAPIFY (A, 5)

文章图片

After MAX-HEAPIFY (A, 1) and i=1l ← 2, r ← 3l≤ heap-size[A] and A [l] > A [i]2≤9 and 84> 5Largest ← 2If r≤ heap-size [A] and A [r] > A [largest]3≤9 and 19< 84If largest (2) ≠1Then Exchange A [1] ←→ A [2]MAX-HEAPIFY (A, 2)

文章图片
优先队列与堆一样, 优先级队列以两种形式出现：最大优先级队列和最小优先级队列。
优先级队列是一种数据结构, 用于维护元素S的集合, 每个元素具有称为键的组合值。最大优先级队列指导以下操作：
INSERT（S, x）：将元素x插入到集合S中, 与操作S =S∪[x]成比例。
MAXIMUM（S）返回具有最高键的S元素。
EXTRACT-MAX（S）删除并返回具有最高键的S元素。
INCREASE-KEY（S, x, k）将元素x的键值增加到新值k, 该值至少与x的当前键值一样大。
让我们讨论如何实现最大优先级队列的操作。过程HEAP-MAXIMUM考虑θ（1）时间的MAXIMUM操作。
最大堆（A） 1.返回A [1]
过程HEAP-EXTRACT-MAX实现EXTRACT-MAX操作。它类似于Heap-Sort过程的for循环。

HEAP-EXTRACT-MAX (A) 1 if A. heap-size < 1 2 error "heap underflow" 3 max ← A [1] 4 A [1] ← A [heap-size [A]] 5 heap-size [A] ← heap-size [A]-1 6 MAX-HEAPIFY (A, 1) 7 return max

过程HEAP-INCREASE-KEY实现了INCREASE-KEY操作。数组中的索引i标识了我们希望增加其键的优先级队列元素。

HEAP-INCREASE-KEY.A, i, key) 1 if key < A[i] 2 errors "new key is smaller than current key" 3 A[i] = key 4 while i> 1 and A [Parent (i)] < A[i] 5 exchange A [i] with A [Parent (i)] 6 i =Parent [i]

HEAP-INCREASE-KEY在n元素堆上的运行时间为O（日志n）, 因为从第3行中更新的节点到根的跟踪路径的长度为O（log n）。
MAX-HEAP-INSERT过程实现INSERT操作。它以要插入到最大堆A中的新项目的键作为输入。该过程首先通过将键为-∞的新叶计算到树上来扩展最大堆。然后, 它调用HEAP-INCREASE-KEY将此新节点的密钥设置为其正确的值并维护max-heap属性