python实现树状大根堆、堆排序、取前k个值
时间: 2023-09-30 21:06:22 浏览: 48
1. 树状大根堆
树状大根堆是一种二叉树,满足以下性质:
1. 每个节点的值都大于等于其子节点的值。
2. 树的最后一层节点都靠左排列。
在Python中,我们可以使用列表来表示二叉树,其中第i个元素的左子节点为2i,右子节点为2i+1,父节点为i//2。
以下是创建树状大根堆的代码:
```python
class MaxHeap:
def __init__(self, arr=None):
self.heap = [0]
if arr:
self.heap.extend(arr)
self._build_heap()
def _build_heap(self):
n = len(self.heap) - 1
for i in range(n // 2, 0, -1):
self._heapify(i)
def _heapify(self, i):
n = len(self.heap) - 1
largest = i
left = 2 * i
right = 2 * i + 1
if left <= n and self.heap[left] > self.heap[largest]:
largest = left
if right <= n and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
self._heapify(largest)
def push(self, val):
self.heap.append(val)
i = len(self.heap) - 1
while i > 1 and self.heap[i] > self.heap[i // 2]:
self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
i //= 2
def pop(self):
if len(self.heap) == 1:
return None
if len(self.heap) == 2:
return self.heap.pop()
root = self.heap[1]
self.heap[1] = self.heap.pop()
self._heapify(1)
return root
```
2. 堆排序
堆排序是一种排序算法,基于树状大根堆实现。其思路是先将数组构建成树状大根堆,然后将堆顶元素与最后一个元素交换,再将前面的元素重新构建成树状大根堆,重复此过程直到数组有序。
以下是堆排序的代码:
```python
def heap_sort(arr):
n = len(arr)
heap = [0] + arr
for i in range(n // 2, 0, -1):
_heapify(heap, i, n)
for i in range(n, 0, -1):
heap[1], heap[i] = heap[i], heap[1]
_heapify(heap, 1, i - 1)
return heap[1:]
def _heapify(heap, i, n):
largest = i
left = 2 * i
right = 2 * i + 1
if left <= n and heap[left] > heap[largest]:
largest = left
if right <= n and heap[right] > heap[largest]:
largest = right
if largest != i:
heap[i], heap[largest] = heap[largest], heap[i]
_heapify(heap, largest, n)
```
3. 取前k个值
在树状大根堆中,堆顶元素是最大的元素,可以通过不断取出堆顶元素来获得最大的k个元素。
以下是取前k个值的代码:
```python
def top_k(arr, k):
n = len(arr)
heap = [0] + arr[:k]
for i in range(k // 2, 0, -1):
_heapify(heap, i, k)
for i in range(k, n):
if arr[i] > heap[1]:
heap[1] = arr[i]
_heapify(heap, 1, k)
return heap[1:]
```
以上是树状大根堆、堆排序和取前k个值的Python实现。