堆性质与数组表示
理解以数组存储的完全二叉树结构，推导父节点和子节点的索引公式，并直观了解上滤与下滤操作。
堆性质与数组表示 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是堆？
堆是一种特殊的完全二叉树，满足堆性质：在最小堆中，每个父节点都小于或等于其子节点；在最大堆中，每个父节点都大于或等于其子节点。该性质保证最小（或最大）元素始终位于根节点，从而可以用 O(1) 时间访问极值元素。堆是优先队列背后的数据结构。
# Min-heap example:
# 1
# / \
# 3 2
# / \ / \
# 7 4 5 6
# Every parent <= its children
# Root (1) is always the minimum
# Max-heap example:
# 9
# / \
# 7 8
# / \ / \
# 3 4 5 6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')完全二叉树结构
堆以完全二叉树的形式存储——除最后一层可能未完全填满外，其余各层都完全填满；最后一层从左到右填充。正是这种结构使得使用数组表示成为可能，既不会浪费空间，也不需要指针。完全二叉树的性质确保堆的高度始终为 floor(log₂ n)，从而保证 push 和 pop 操作的时间复杂度为 O(log n)。
# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))
# NOT complete (last level not left-filled):
# 1
# / \
# 2 3
# \
# 4 <- right child without left sibling
# Valid complete binary tree with 4 nodes:
# 1
# / \
# 2 3
# /
# 4
print('Complete BT: height = floor(log2(n)) always')堆的数组表示
完全二叉树结构使堆可以存储在普通的数组中且无需任何指针。对于索引为 i 的节点（索引从 0 开始），其父节点位于 (i-1) // 2，左子节点位于 2i+1，右子节点位于 2i+2。这种整数运算取代了指针遍历，使堆具有极佳的缓存友好性。
# Array representation (0-indexed):
# Index: 0 1 2 3 4 5 6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree: 1 (index 0)
# / \
# 3 2 (indices 1, 2)
# / \ / \
# 7 4 5 6 (indices 3,4,5,6)
# Index formulas (0-based):
def parent(i): return (i - 1) // 2
def left_child(i): return 2 * i + 1
def right_child(i): return 2 * i + 2
heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])上滤：插入后恢复堆
上滤（也称为上浮或向上堆化）用于在堆数组末尾插入新元素之后。将新元素与其父节点进行比较；如果违反堆性质，就交换二者并继续向上调整。重复此过程，直到元素处于正确位置或到达根节点。由于树高为 O(log n)，该操作的时间复杂度为 O(log n)。
def sift_up(heap, i):
while i > 0:
p = (i - 1) // 2 # parent index
if heap[p] > heap[i]: # min-heap: parent should be smaller
heap[p], heap[i] = heap[i], heap[p]
i = p
else:
break # heap property restored
# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0) # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap) # 0 should bubble to root下滤：弹出后恢复堆
下滤（向下堆化）用于移除根节点之后。将最后一个元素移到根节点，然后通过反复与较小的子节点交换将它向下移动（对于最小堆），直到恢复堆性质。该操作的时间复杂度同样为 O(log n)。上滤和下滤是所有堆操作的基础构件。
def sift_down(heap, i, n):
while True:
smallest = i
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child
if l < n and heap[l] < heap[smallest]:
smallest = l
if r < n and heap[r] < heap[smallest]:
smallest = r
if smallest == i:
break # already in correct position
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap) # valid min-heap again从数组构建堆：弗洛伊德算法
逐个插入 n 个元素的朴素方法的时间复杂度为 O(n log n)。弗洛伊德的 heapify 算法通过对每个非叶子节点应用下滤，在 O(n) 时间内构建堆：从最后一个非叶子节点（索引 n//2 - 1）开始，反向处理直到根节点。叶子节点本身已经是简单的堆，因此我们只需修正内部节点——这就是总工作量为 O(n) 而不是 O(n log n) 的原因。
def build_heap(arr):
n = len(arr)
# Start from last non-leaf node: index n//2 - 1
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, i, n)
return arr
arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr) # root should be 1
# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).使用数组堆进行堆排序
堆排序的时间复杂度为 O(n log n)，额外空间复杂度为 O(1)。阶段 1：在 O(n) 时间内从数组构建最大堆。阶段 2：反复提取最大值，方法是将根节点与最后一个未排序元素交换，然后在缩小后的堆上执行下滤。经过 n 次提取后，数组将按升序排列。这种原地算法展示了数组表示如何在不分配单独数据结构的情况下实现排序。
def sift_down_max(arr, i, n):
while True:
largest = i
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]: largest = l
if r < n and arr[r] > arr[largest]: largest = r
if largest == i: break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heap_sort(arr):
n = len(arr)
# Build max-heap
for i in range(n // 2 - 1, -1, -1):
sift_down_max(arr, i, n)
# Extract elements one by one
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0] # move max to end
sift_down_max(arr, 0, end)
arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr) # [1, 2, 3, 5, 7, 8, 9]最小堆与最大堆
最小堆的根节点是最小元素；弹出操作总是得到最小值。最大堆的根节点是最大元素；弹出操作总是得到最大值。二者的结构和操作完全相同，区别只在于比较方向。Python 的 heapq 模块只实现了最小堆，因此必须对值取相反数来模拟最大堆。
import heapq
# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap)) # 1
# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap max:', -heapq.heappop(max_heap)) # 5 (negate on pop)
# For tuples: heapq sorts by first element
print(min_heap, max_heap)堆操作复杂度总结
所有堆操作都建立在上滤和下滤之上，这两者的时间复杂度均为 O(log n)。推入：append + 上滤 = O(log n)。弹出：将根节点与最后一个元素交换 + 下滤 = O(log n)。查看堆顶：访问索引 0 = O(1)。构建堆：通过弗洛伊德算法实现，复杂度为 O(n)。堆排序：O(n log n)。当您需要反复获取动态集合中的最小值或最大值时，这些复杂度使堆成为理想的数据结构。
# Heap complexity summary:
# Operation | Time | Space
# --------------|------------|-------
# Push | O(log n) | O(1)
# Pop (min/max) | O(log n) | O(1)
# Peek | O(1) | O(1)
# Build from n | O(n) | O(1) in-place
# Heap sort | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)
import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data)) # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data)) # [1, 2, 3]面试中的实用堆模式
堆可以通过一种通用模式解决一系列面试题：在遍历 n 个元素的流时，维护一个包含 k 个候选项的优先队列。出现频率最高的 k 个元素、距离原点最近的 k 个点以及任务调度器都使用了这种模式。当您看到“给定包含 n 个项目的数据流，维护其中最优的 k 个”时，就应当识别出这种模式——这通常需要一个大小为 k 的堆，总时间复杂度为 O(n log k)。
import heapq
# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
# Use max-heap (negate distance) of size k
heap = []
for x, y in points:
dist = -(x*x + y*y) # negate for max-heap
heapq.heappush(heap, (dist, x, y))
if len(heap) > k:
heapq.heappop(heap) # remove farthest
return [[x, y] for _, x, y in heap]
points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2)) # 2 closest to origin堆与有序数组的取舍
当您只需要反复访问最小值或最大值，且集合会动态变化时，应选择堆。当您需要按索引随机访问或执行范围查询时，应选择有序数组。堆的弱点是搜索任意元素需要 O(n) 时间；它的优势是插入和删除只需 O(log n) 时间，访问最小值或最大值只需 O(1) 时间。有序数组的插入需要 O(n) 时间，但可以通过二分搜索在 O(log n) 时间内完成搜索。
# Trade-off comparison:
# Structure | insert | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap | O(logn) | O(logn) | O(n) | O(n)
# Sorted array | O(n) | O(n) | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn) | O(logn)| O(logn+k)
# Hash map | O(1) | O(1) | O(1) | O(n)
# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')快速检查
测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中您学习了：堆性质和完全二叉树结构，带有父子节点索引公式的数组表示，以及作为所有堆操作基础构件的上滤和下滤，包括弗洛伊德的 O(n) 构建算法。接下来我们将实现 heapify，并探索 Python 的 heapq 模块。
常见问题解答
「堆性质与数组表示」课时是免费的吗？
是的 — 「堆性质与数组表示」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「堆性质与数组表示」这节课中我会学到什么？
理解以数组存储的完全二叉树结构，推导父节点和子节点的索引公式，并直观了解上滤与下滤操作。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「堆性质与数组表示」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。