摘要：
堆（Heap）是一种特殊的数据结构，它是一种近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点。堆常用于解决一些需要频繁查找最大（或最小）元素的问题。本文将围绕堆的经典问题——前K个元素和合并K个链表，探讨堆在算法中的应用。
一、
堆是一种非常重要的数据结构，它在计算机科学中有着广泛的应用。本文将重点介绍堆在解决前K个元素和合并K个链表这两个经典问题中的应用。
二、堆的基本概念
1. 堆的定义
堆是一种近似完全二叉树的结构，同时满足堆积的性质。堆积性质有以下两种形式：
（1）大根堆：每个父节点的值都大于或等于其子节点的值。
（2）小根堆：每个父节点的值都小于或等于其子节点的值。
2. 堆的存储结构
堆通常使用数组来存储，假设堆的根节点存储在数组中的索引为0，则对于任意节点i，其左子节点的索引为2i+1，右子节点的索引为2i+2，父节点的索引为(i-1)/2。
三、前K个元素问题
1. 问题描述
给定一个整数数组arr，找出数组中前K个最大的元素。
2. 解决方案
（1）使用大根堆
我们可以将数组arr的前K个元素构建成一个最大堆，然后依次弹出堆顶元素，即可得到前K个最大的元素。
（2）代码实现
python
def build_max_heap(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
def heapify(arr, n, i):
largest = i
l = 2 i + 1
r = 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:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def find_k_largest_elements(arr, k):
n = len(arr)
build_max_heap(arr)
result = []
for i in range(k):
result.append(arr[0])
arr[0], arr[n - 1 - i] = arr[n - 1 - i], arr[0]
n -= 1
heapify(arr, n, 0)
return result
测试代码
arr = [3, 2, 1, 5, 6, 4]
k = 2
print(find_k_largest_elements(arr, k)) 输出：[6, 5]
四、合并K个链表问题
1. 问题描述
给定K个单链表，每个链表中的元素都是整数，要求合并这些链表，并返回一个排序后的链表。
2. 解决方案
（1）使用小根堆
我们可以将K个链表的头部节点构建成一个最小堆，然后依次弹出堆顶元素，将弹出的元素插入到新的链表中，并更新堆。
（2）代码实现
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_min_heap(heads):
heap = []
for head in heads:
if head:
heap.append(head)
heap.sort(key=lambda x: x.val)
return heap
def heapify(heap):
n = len(heap)
for i in range(n // 2 - 1, -1, -1):
heapify(heap, i, n)
def merge_k_sorted_lists(heads):
heap = build_min_heap(heads)
dummy = ListNode()
current = dummy
while heap:
node = heap.pop(0)
current.next = node
current = current.next
if node.next:
heap.append(node.next)
heapify(heap)
return dummy.next
测试代码
heads = [
ListNode(1, ListNode(4, ListNode(5))),
ListNode(1, ListNode(3, ListNode(4))),
ListNode(2, ListNode(6))
]
merged_list = merge_k_sorted_lists(heads)
while merged_list:
print(merged_list.val, end=' ')
merged_list = merged_list.next
输出：1 1 2 3 4 4 5 6
五、总结
本文介绍了堆数据结构在解决前K个元素和合并K个链表这两个经典问题中的应用。通过使用堆，我们可以高效地找到前K个最大元素和合并K个排序链表。在实际应用中，堆是一种非常实用的数据结构，具有广泛的应用前景。
Comments NOTHING