计算机专业面试常见数据结构中的堆（Heap）是什么？

一、什么是堆（Heap）？

堆（Heap）是一种特殊的完全二叉树，它满足堆的性质。堆分为最大堆和最小堆两种类型。在最大堆中，每个父节点的值都大于或等于其子节点的值；在最小堆中，每个父节点的值都小于或等于其子节点的值。堆用于优先队列的实现，如最短路径搜索算法中的优先队列。

二、堆的性质

1. 完全二叉树：堆是一个完全二叉树，即除了最底层外，其他层都被完全填满，最底层从左到右填满。

2. 堆性质：对于最大堆，任意节点的值都大于或等于其子节点的值；对于最小堆，任意节点的值都小于或等于其子节点的值。

3. 父子关系：对于任意节点，其父节点的位置是它的索引整除以2（即 parent[i] = i / 2），其子节点的位置是它的索引乘以2和乘以2加1（即 left[i] = 2 * i + 1, right[i] = 2 * i + 2）。

三、堆的应用

1. 优先队列：堆常用于实现优先队列，最大堆用于实现最小优先队列，最小堆用于实现最大优先队列。

2. 最短路径算法：如Dijkstra算法，可以使用堆来存储待访问的节点，从而快速找到最短路径。

3. 最小（或最大）堆排序：堆排序算法是基于堆的一种排序算法，其时间复杂度为O(nlogn)。

4. 查找如查找未排序数组中的第k大元素，可以使用最大堆来存储前k个元素，每次弹出最大元素，直到找到第k个元素。

四、堆的构建与调整

1. 构建堆：将无序序列构造成堆的过程称为堆化。最大堆的堆化可以通过从一个非叶子节点开始向上调整其父节点和子节点的关系来实现。

2. 调整堆：当插入或删除元素后，需要调整堆，使其重新满足堆的性质。最大堆的调整可以通过比较父节点和子节点的值，将较小的子节点交换到父节点位置，继续向上调整。

五、堆的代码实现

是一个简单的最大堆的Python代码实现：

python

class MaxHeap:

def __init__(self):

self.heap = []

def parent(self, i):

return (i – 1) // 2

def insert(self, key):

self.heap.append(key)

self._heapify_up(len(self.heap) – 1)

def _heapify_up(self, i):

while i > 0 and self.heap[self.parent(i)] < self.heap[i]:

self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]

i = self.parent(i)

def extract_max(self):

if len(self.heap) < 1:

return None

root = self.heap[0]

self.heap[0] = self.heap.pop()

self._heapify_down(0)

return root

def _heapify_down(self, i):

l = 2 * i + 1

r = 2 * i + 2

largest = i

if l < len(self.heap) and self.heap[l] > self.heap[largest]:

largest = l

if r < len(self.heap) and self.heap[r] > self.heap[largest]:

largest = r

if largest != i:

self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]

self._heapify_down(largest)

# Example usage

max_heap = MaxHeap()

max_heap.insert(3)

max_heap.insert(1)

max_heap.insert(6)

max_heap.insert(5)

max_heap.insert(2)

print(max_heap.extract_max()) # Output: 6

六、

堆是计算机科学中一种重要的数据结构，它在许多算法中都有广泛的应用。理解堆的性质、构建和调整方法对于计算机专业毕业生来说是非常重要的。通过掌握堆的知识，可以更好地应对面试中的相关。