编程珠玑小根堆
时间: 2023-06-29 13:05:01 浏览: 44
小根堆是一种常用的数据结构,它可以用来在一个未排序的数组中找到最小的 k 个元素,或者用来排序一个数组。下面是一个简单的实现小根堆的代码:
```python
class MinHeap:
def __init__(self, maxsize=None):
self.maxsize = maxsize
self._elements = [None] * (maxsize + 1)
self._count = 0
def __len__(self):
return self._count
def add(self, value):
if self._count + 1 <= self.maxsize:
self._count += 1
self._elements[self._count] = value
self._siftup(self._count)
def _swap(self, i, j):
self._elements[i], self._elements[j] = self._elements[j], self._elements[i]
def _siftdown(self, idx):
left = idx * 2
right = idx * 2 + 1
smallest = idx
if left <= self._count and self._elements[left] < self._elements[smallest]:
smallest = left
if right <= self._count and self._elements[right] < self._elements[smallest]:
smallest = right
if smallest != idx:
self._swap(idx, smallest)
self._siftdown(smallest)
def _siftup(self, idx):
parent = idx // 2
if parent > 0 and self._elements[idx] < self._elements[parent]:
self._swap(idx, parent)
self._siftup(parent)
def extract(self):
if self._count > 0:
value = self._elements[1]
self._elements[1] = self._elements[self._count]
self._count -= 1
self._siftdown(1)
return value
```
这里我们实现了一个最小堆,它可以用来找到一个未排序的数组中最小的 k 个元素。我们可以先将数组中的前 k 个元素加入到堆中,然后把剩下的元素逐个与堆顶元素进行比较,如果比堆顶元素小,则把堆顶元素替换为该元素,并进行下滤操作。最终堆中的元素就是最小的 k 个元素。