堆排序

堆的数据结构和相关性质

逻辑结构为一个近似完全二叉树,具有完全二叉树的性质

物理结构为数组

A.length为数组中元素的个数

A.heap-size为存放在数组A中的堆的元素个数

A.length≥A.heap-size

对于某二叉树中的节点i,对应到数组A中的索引位置:

  1. i的父节点为⌊i/2⌋(向下取整)
  2. i的左子节点为2i
  3. i的右子节点为2i+1

注意:这里的乘除2的操作在实际代码中可以使用左移右移操作来提高效率

最大堆:A[PARENT(i)]≥A[i]
最小堆:A[PARENT(i)]≤A[i]

只能保证树根是最大的或最小的!!!

最大堆

MAX-HEAPIFY

维护最大堆的性质

输入为数组A和下标i,以及堆的元素个数A.heap-size

一个很重要的假定:假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆。即对于i来讲,它的左右子树已经都是最大堆了。

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
MAX-HEAPIFY
*/

l = LEFT(i)
r = RIGHT(i)

if l <= A.heap-size and A[l]>A[i]
largest = l
else
largest = i

if r <= A.heap-size and A[r] > A[i]
largest = r

if largest != i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)

对于一个数高为h的节点来说,MAX-HEAPIFY的时间复杂度为O(h)

BUILD-MAX-HEAP

建堆

对于大小为n的数组A[1..n]来说,子数组A(⌊n/2⌋+1..n)中的元素都是树的叶子节点

输入一个数组A

伪代码:

1
2
3
4
5
6
7
8
/**
BUILD-MAX-HEAP
*/

A.heap-size = A.length

for i = ⌊A.length/2⌋ downto 1
MAX-HEAPIFY(A, i)

时间复杂度为O(n),即可以在线性时间内讲一个无序数组构造成一个最大堆

HEAPSORT

伪代码:

1
2
3
4
5
6
7
8
9
/**
HEAPSORT
*/

BUILD-MAX-HEAP[A]
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size -= 1
MAX-HEAPIFY(A, 1)

MAX-HEAP-INSERT

HEAP-EXTRACT-MAX

HEAP-INCREASE-KEY

HEAP-MAXIMUM

最小堆

MIN-HEAPIFY

BUILD-MINHEAP

HEAPSORT

MIN-HEAP-INSERT

HEAP-EXTRACT-MIN

HEAP-DECREASE-KEY

HEAP-MINIMUM

文章作者: ゴウサク
文章链接: http://dapaner.top/2021/08/07/堆排序/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Corner&Coder
微信赞赏码
支付宝赞赏码