Python 堆排序

概述

堆排序是一种高效的排序算法，它基于二叉堆的数据结构，并且具有稳定性和稳定性。堆排序的主要思想是将待排序的数据构建成一个二叉堆，并且通过不断调整堆的结构，最终得到有序的序列。

二叉堆

二叉堆是一种特殊的二叉树，它满足以下两个条件：

• 父节点的键值总是大于等于或小于等于子节点的键值（最大堆或最小堆）。
• 二叉堆是一颗完全二叉树。

在堆排序中，我们将使用最大堆（父节点的键值总是大于等于子节点的键值）。

实现一个最大堆

我们可以使用数组来实现一个最大堆。数组的索引从0开始，如果某个节点的索引为i，则它的父节点的索引为(i-1)//2，左子节点的索引为2i+1，右子节点的索引为2i+2。

下面是一个最大堆的实现示例代码：

class MaxHeap:
    def __init__(self):
        self.heap = []

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

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, k):
        self.heap.append(k)
        self.heapify_up(len(self.heap) - 1)

    def delete(self, i):
        self.heap[i] = float('inf')
        self.heapify_up(i)
        self.extract_max()

    def extract_max(self):
        if len(self.heap) == 0:
            return None
        max_value = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return max_value

    def heapify_up(self, i):
        while i != 0 and self.heap[i] > self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def heapify_down(self, i):
        max_index = i
        l = self.left_child(i)
        r = self.right_child(i)
        if l < len(self.heap) and self.heap[l] > self.heap[max_index]:
            max_index = l
        if r < len(self.heap) and self.heap[r] > self.heap[max_index]:
            max_index = r
        if i != max_index:
            self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]
            self.heapify_down(max_index)

堆排序算法

堆排序算法主要分为两个步骤：
1. 构建堆：将待排序的序列构建为一个二叉堆。
2. 交换元素：交换堆顶元素（最大元素）与最后一个元素，并将剩余元素重新构建堆，重复此过程直到序列有序。

下面是堆排序算法的实现示例代码：

def heap_sort(arr):
    n = len(arr)
    max_heap = MaxHeap()

    # 构建堆
    for i in range(n):
        max_heap.insert(arr[i])

    # 交换元素，重建堆
    for i in range(n - 1, -1, -1):
        arr[i] = max_heap.extract_max()

    return arr

示例

假设有一个待排序的序列：[4, 10, 3, 5, 1]，我们可以使用堆排序算法对其进行排序。

arr = [4, 10, 3, 5, 1]

sorted_arr = heap_sort(arr)

print(sorted_arr)

输出结果为：

[1, 3, 4, 5, 10]

性能分析

时间复杂度

堆排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。

空间复杂度

堆排序的空间复杂度为O(1)，即只需要使用常量级别的额外空间。

稳定性

堆排序是一种不稳定的排序算法，即相同的元素在排序后可能会改变顺序。

总结

堆排序是一种高效且不稳定的排序算法，它基于二叉堆的数据结构。该算法的主要思想是通过不断调整堆的结构，将最大（或最小）元素交换到堆顶，并将剩余元素重新构建堆，从而达到排序的目的。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。虽然它不具备稳定性，但由于其优秀的时间复杂度和空间复杂度，堆排序在实际应用中得到了广泛的应用。