堆排序是一种非常常用的排序算法，而堆数据结构中的大顶堆和小顶堆也是非常重要的基础概念。在本文中，我们将从以下几个方面分别进行详细的阐述：
一、堆的基本概念
堆可以看作是一种特殊的完全二叉树，其每个节点都大于或小于其子节点。大顶堆是指每个节点的值都大于或等于其子节点的值，小顶堆则相反，每个节点的值都小于或等于其子节点的值。
堆可以使用数组或 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 < len(heap) else None
if right_child_index and heap[right_child_index] > 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_size and heap[left_child_index] > heap[largest]:
largest = left_child_index
if heap_size is not None and right_child_index < heap_size and heap[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) < k:
heap.append(i)
build_heap(heap)
elif i > 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]
堆数据结构的应用极为广泛，同时也是算法面试中经常出现的题目，因此掌握堆的基本概念和操作方式，对我们的编程发展和提升都有着非常重要的作用。
