【算法导论】堆排序

堆排序的时间复杂度为O(nlgn)，具有原址性。

同时需要区分“垃圾收集存储机制”中的堆，例如Java语言中的定义，这里的堆不是垃圾收集存储，只是一种数据结构。

1.堆

如下图是一个二叉堆：

二叉堆可以分为两种形式：最大堆和最小堆。

最大堆从根到叶子节点递减（常用于排序），最小堆是从根到叶子节点递增（常用于构造优先队列）。

2 维护堆的性质

当新的数据被插入时，理所应当需要维护这个树，让他保持堆的性质：

代码如下，时间复杂度为O(lgn)：

def max_heapify(self, heap_list, i):
    """
    调整最大堆
    :param heap_list:需要被调整的队列
    :param i: 需要被调整的节点
    :return:
    """
    list_length = len(heap_list)
    # 分别计算左孩子和右孩子索引
    left_point_index = 2 * i
    right_point_index = left_point_index + 1
    # 判断左孩子是否比根节点大，如果大，说明左子树需要调整
    if left_point_index < list_length and heap_list[left_point_index] > heap_list[i]:
        largest = left_point_index
    # 如果左孩子比根节点小，说明左子树为最大堆
    else:
        largest = i
    # 判断右子树是否需要调整
    if right_point_index < list_length and heap_list[right_point_index] > heap_list[largest]:
        largest = right_point_index
    # 如果需要调整，交换两个索引中的数并继续向下调整子树
    if largest != i:
        temp = heap_list[largest]
        heap_list[largest] = heap_list[i]
        heap_list[i] = temp
        self.max_heapify(heap_list, largest)
    return heap_list

3.建堆

建堆可以视为进行n次调整堆的过程，同时，可以只遍历前半,因为满二叉树的性质决定了后一半为叶子节点，可以视为已经排好序。

代码如下，时间复杂度为O(n)：

def build_max_heap(self, init_list):
    """
    构建最大堆
    :param init_list: 列表
    :return:
    """
    max_heap = []
    # 这里可以遍历全部数组，也可以只遍历前半,因为满二叉树的性质决定了后一半为叶子节点，可以视为已经排好序
    for i in range(int(len(init_list) / 2), 0, -1):
        max_heap = self.max_heapify(init_list, i)
        print(max_heap)
    return max_heap

4.堆排序算法

最大堆的根永远都是列表中最大的数，因此如果在不需要全排列的情况下，堆排序是个很好的选择。

代码如下，时间复杂度为O(nlgn):

def heap_sort(self, init_list):
    """
    堆排序
    :param init_list: 列表
    :return:
    """
    sort_list = []
    # 进行第一次堆排序
    max_heap = self.build_max_heap(init_list)
    # 将第一次排序的首元素加到排序列表中（下标从1开始）
    # sort_list.append(max_heap[1])
    # 取出第一个数并继续进行堆排序
    for i in range(len(init_list)):
        max_heap = max_heap[1:]
        # 如果堆大小只剩1，输出最后一个元素
        if len(max_heap) == 1:
            sort_list.append(max_heap[0])
            return sort_list
        # 获取新堆，并将根节点添加到排序列表中
        sort_list.append(self.build_max_heap(max_heap)[0])

5.优先队列

我们只需要执行一次最大堆操作（self.build_max_heap(max_heap)）就可以知道当前队列中优先级最高的元素是什么（O(lgn)），当有新的任务进入队列时，我们也只需要简单的维护一下最大堆就可以让整个系统顺利运行（O(lgn)）