堆排序

堆

堆是一个数组，存储在数组中的二叉树。堆可以看成一个近似的完全二叉树，除了最底层外，该树是充满的。

堆可以分为两类：

• 最大堆：父节点 > 子节点
• 最小堆：父节点 < 子节点

---

堆排序

堆排序的时间复杂度也是 O(n·lgn)。但是，不同于归并排序，堆排序具有空间原址性：只需要常数个额外空间来存储临时数据。

为了实现堆，我们要实现以下两个函数：

• MAX-HEAPIFY()：最大堆化函数，时间复杂度 **O(lgn)**。
• BUILD-MAX-HEAP()：建立最大堆函数，时间复杂度 **O(n)**。

---

堆化

# python代码
# A: List of elements in the heap
# i: Index of the element to check
# n: Total number of elements in the heap
def max_heapify(A, i, n):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # i's left child
    right = 2 * i + 2  # i's right child

    # If left child is larger than root
    if left < n and A[left] > A[largest]:
        largest = left

    # If right child is larger than the largest so far
    if right < n and A[right] > A[largest]:
        largest = right

    # If largest is not root
    if largest != i:
        A[i], A[largest] = A[largest], A[i]  # Swap
        max_heapify(A, largest, n)  # Recursively heapify the affected sub-tree

需要注意：当对 i 节点调用MAX-HEAPIFY()时，只有当其左右子树都是最大堆时，调用后，i 节点开始的树才是最大堆。

直观上，不难发现MAX-HEAPIFY()的时间复杂度是：**O(lgn)**。

---

建堆

# python代码
def build_max_heap(A):
    n = len(A)
    A.heap_size = n  # Set the heap size
    # Start from the last non-leaf node and move upwards
    for i in range(n // 2 - 1, -1, -1):
        max_heapify(A, i, n)

粗略的看，每次调用max_heapify()函数的时间开销是**O(lgn)，总共调用了O(n)次，所以build_max_heap()的时间复杂度应该是：O(n·lgn)**。

但是由于：底层节点调用max_heapify()的时间复杂度实际上是**O(h)，远远小于O(n)，且底层节点数量更多，时间开销接近O(lgn)的高层节点数量很少。所以，build-max-heap()的时间复杂度比O(n·lgn)更小，是O(n)**。

推导如下：

高度为h的节点最多有 [n/2^h+1] 个。

因此，我们可以在线性时间内，把一个无序数组构造成为一个最大堆。

---

堆排序

堆排序的过程：

• 在整个数组上建立最大堆。
• 数组的第一个元素（待排序序列中的最大元素），与待排序序列的最后一个元素交换。
• 堆大小（也是待排序序列长度）减1。
• 对堆顶元素（数组第一个元素）调用max_heapify函数，保证新的堆仍是最大堆。
• 如此，排好了原序列中的最大元素，且新序列仍是最大堆。如此循环即可。

# python代码
def heapsort(A):
    build_max_heap(A)  # Build the max heap
    for i in range(len(A), 1, -1):
        A[0], A[i-1] = A[i-1], A[0]  # Swap the root with the last element
        A.heap_size -= 1  # Decrease the heap size
        max_heapify(A, 0, i-1)  # Heapify the root

堆排序的时间复杂度：**O(n·lgn)**。

---

优先队列

优先队列是一种数据结构，维护由一组元素，支持插入和删除最大元素（或最小元素）。

一个最大优先队列支持以下操作：

函数	描述	时间
INSERT(S,x)	把元素 x 插入集合 S 中。	O(lgn)
MAXIMUM(S)	返回 S 中具有最大元素。	O(1)
EXTRACT-MAX(S)	去掉并返回 S 中的具有最大元素。	O(lgn)
INCREASE-KEY(S, x, k)	将元素 x 增加到 k（假设k>x）	O(lgn)

需要注意：

• 堆并不一定是是二叉堆，二叉堆只是常见且易于用数组实现而已。
• 最大堆（二叉堆）只是优先队列的一种实现方式。

# python code
#（这里省略了class heap的类定义）

# MAXIMUM(S)
# 返回堆顶元素即可
def heap_maximum(A):
    if A.heap_size < 1:
        raise ValueError("Heap is empty")
    return A[0]

# EXTRACT-MAX(S)
# 返回并删除堆顶元素，再对堆顶元素调用max_heapify()
def heap_extract_max(A):
    if A.heap_size < 1:
        raise ValueError("Heap underflow")
    max_value = A[0]
    A[0] = A[A.heap_size - 1]
    A.heap_size -= 1
    max_heapify(A, 0, A.heap_size)
    return max_value

def parent(i):
    return (i - 1) // 2

# INCREASE-KEY(S, x, k)
# 将A[i]赋值为k，并往上逐个检查：是否大于父节点，若大于则交换。
def heap_increase_key(A, i, key):
    if key < A[i]:
        raise ValueError("New key is smaller than current key")
    A[i] = key
    while i > 1 and A[parent(i)] < A[i]:
        A[i], A[parent(i)] = A[parent(i)], A[i]  # Swap with parent
        i = parent(i)
        
# INSERT(S,x)
# 在堆末尾插入负无穷，再调用heap_increase_key()将负无穷变为x，从而实现插入。
def max_heap_insert(A, key):
    A.heap_size += 1
    A[A.heap_size - 1] = float('-inf')  # Set the new leaf node with a very small value
    heap_increase_key(A, A.heap_size - 1, key)