堆的基本存储学习笔记

什么是堆？

堆（Heap）是一种非线性数据结构，它是一棵完全二叉树。堆分为大根堆和小根堆两种。在大根堆中，每个父节点的值都比子节点的值要大；而在小根堆中，每个父节点的值都比子节点的值要小。

堆的基本操作

插入元素

堆的插入操作是将新元素插入到堆的末尾，然后从下往上比较元素的大小，直到找到该元素应该在的位置。具体实现可以使用“上滤”操作来维护堆的性质。

pythonCopy Code
def insert(heap, x):
    heap.append(x)
    i = len(heap) - 1
    while i > 0 and heap[(i-1)//2] < heap[i]:
        heap[(i-1)//2], heap[i] = heap[i], heap[(i-1)//2]
        i = (i-1) // 2

删除元素

堆的删除操作是将堆顶元素删除，并将堆的最后一个元素移动到堆顶，然后从上往下比较元素的大小，直到找到该元素应该在的位置。具体实现可以使用“下滤”操作来维护堆的性质。

pythonCopy Code
def extract_max(heap):
    if len(heap) == 0:
        return None
    max_val = heap[0]
    heap[0] = heap[-1]
    heap.pop()
    i = 0
    while True:
        l = 2 * i + 1
        r = 2 * i + 2
        max_index = i
        if l < len(heap) and heap[l] > heap[max_index]:
            max_index = l
        if r < len(heap) and heap[r] > heap[max_index]:
            max_index = r
        if max_index == i:
            break
        heap[i], heap[max_index] = heap[max_index], heap[i]
        i = max_index
    return max_val

堆的实例：堆排序

堆排序（Heap Sort）是一种利用堆进行排序的算法。堆排序的基本思想是将待排序的序列构造成一个大根堆（或小根堆），然后依次取出堆顶元素，直到堆为空。

pythonCopy Code
def heap_sort(nums):
    # 构建大根堆
    n = len(nums)
    for i in range(n//2-1, -1, -1):
        adjust_heap(nums, i, n)
    # 依次取出堆顶元素
    for i in range(n-1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        adjust_heap(nums, 0, i)
        
def adjust_heap(nums, i, n):
    while True:
        l = 2 * i + 1
        r = 2 * i + 2
        max_index = i
        if l < n and nums[l] > nums[max_index]:
            max_index = l
        if r < n and nums[r] > nums[max_index]:
            max_index = r
        if max_index == i:
            break
        nums[i], nums[max_index] = nums[max_index], nums[i]
        i = max_index

以上是堆的基本存储学习笔记，并且介绍了堆的基本操作和实例。