全面了解大顶堆和小顶堆的实现和应用

堆排序是一种非常常用的排序算法，而堆数据结构中的大顶堆和小顶堆也是非常重要的基础概念。在本文中，我们将从以下几个方面分别进行详细的阐述：

一、堆的基本概念

堆可以看作是一种特殊的完全二叉树，其每个节点都大于或小于其子节点。大顶堆是指每个节点的值都大于或等于其子节点的值，小顶堆则相反，每个节点的值都小于或等于其子节点的值。

堆可以使用数组或 linked list 来进行实现。在数组中，当我们要获取一个节点的左子节点或右子节点时，可以利用以下公式：

    left_child_index = 2 * node_index + 1;
    right_child_index = 2 * node_index + 2;

而在 linked list 中，我们可以通过链表中的 next 指针来获取左子节点和右子节点。

二、堆的基本操作

堆的基本操作包括：插入节点、删除节点、堆化（或称为下滤）和建堆。

插入节点：将新节点插入堆的末尾，然后将该节点上移，以保证堆的特性。

    def insert(heap, item):
        heap.append(item)
        node_index = len(heap) - 1
        while node_index > 0 and heap[(node_index-1)//2] < heap[node_index]:
            heap[(node_index-1)//2], heap[node_index] = heap[node_index], heap[(node_index-1)//2]
            node_index = (node_index-1)//2

删除节点：将堆顶节点删除，然后用最后一个节点来替换该节点，最后将新的节点下移，以保证堆的特性。

    def delete(heap):
        if len(heap) == 0:
            return None
        if len(heap) == 1:
            return heap.pop()
        item = heap[0]
        heap[0] = heap.pop()
        node_index = 0
        child_index = 2 * node_index + 1
        while child_index < len(heap):
            right_child_index = child_index+1 if child_index+1  heap[child_index]:
                child_index = right_child_index
            if heap[node_index] < heap[child_index]:
                heap[node_index], heap[child_index] = heap[child_index], heap[node_index]
                node_index = child_index
                child_index = 2 * node_index + 1
            else:
                break
        return item

堆化（下滤）：将一个节点下移，直到其达到正确的位置，以保证堆的特性。

    def heapify(heap, node_index, heap_size=None):
        left_child_index = 2 * node_index + 1
        right_child_index = 2 * node_index + 2
        largest = node_index
        if heap_size is not None and left_child_index  heap[largest]:
            largest = left_child_index
        if heap_size is not None and right_child_index  heap[largest]:
            largest = right_child_index
        if largest != node_index:
            heap[node_index], heap[largest] = heap[largest], heap[node_index]
            heapify(heap, largest)

建堆：建立一个堆，可以使用插入节点的方法，也可以使用堆化方法。其中，使用堆化方法建堆的时间复杂度是 O(n)，而使用插入节点的方法建堆的时间复杂度为 O(nlogn)。

    def build_heap(heap, heap_size=None):
        n = len(heap) if heap_size is None else heap_size
        for i in range(n//2-1, -1, -1):
            heapify(heap, i, heap_size=heap_size)

三、堆的应用

1. 堆排序

堆排序主要分为两个步骤，首先使用建堆方法建立一个堆，然后，不断地将堆顶元素取出，放入已排序部分中，然后重新调整剩余元素组成的堆。

    def heap_sort(array):
        n = len(array)
        for i in range(n-1, 0, -1):
            array[0], array[i] = array[i], array[0]
            heapify(array, node_index=0, heap_size=i)
        return array

2. Top K 问题

Top K 问题即在一个集合中找到前 K 大的元素，在堆数据结构中，可以使用一个 K 大小的小顶堆来解决，由于小顶堆只保留 K 个元素，每次遍历集合中的一个元素， 如果该元素大于堆顶元素，则将堆顶元素删除，并插入该元素。

    def find_top_k(array, k):
        heap = []
        for i in array:
            if len(heap)  heap[0]:
                heap[0] = i
                heapify(heap, 0)
        return heap

3、求中位数

在一个数据流中，经常需要求其中位数，即将该数据流排好序之后，中间位置的数。使用两个堆可以方便地解决该问题。

我们可以使用一个小顶堆和一个大顶堆，其中，大顶堆存储数据流中较小的一半数据，小顶堆中存储数据流中较大的一半数据。中位数因为是两堆顶元素的平均数或者大顶堆顶，因此可以通过判断两堆大小来确定中位数的取值。

    class MedianFinder:
        def __init__(self):
            self.max_heap = []
            self.min_heap = []

        def add_num(self, num):
            if len(self.max_heap) == len(self.min_heap):
                if self.min_heap and num > self.min_heap[0]:
                    num = heapq.heappushpop(self.min_heap,num)
                heapq.heappush(self.max_heap,-num)
            else:
                if num < -self.max_heap[0]:
                    num = -heapq.heappushpop(self.max_heap,-num)
                heapq.heappush(self.min_heap,num)

        def find_median(self):
            if len(self.max_heap) == len(self.min_heap):
                return (-self.max_heap[0] + self.min_heap[0]) / 2.0
            else:
                return -self.max_heap[0]

堆数据结构的应用极为广泛，同时也是算法面试中经常出现的题目，因此掌握堆的基本概念和操作方式，对我们的编程发展和提升都有着非常重要的作用。