最小堆插入元素和删除堆顶(无哨兵元素)
时间: 2024-03-14 18:36:03 浏览: 86
最小堆的基本操作
最小堆是一种二叉树,满足以下两个条件:
1. 任意节点的值都小于或等于其子节点的值;
2. 是一棵完全二叉树。
实现最小堆的关键是维护堆的性质,即任意节点的值都小于或等于其子节点的值。
插入元素时,需要先将新元素插入到堆的末尾,然后通过不断将其与其父节点比较交换的方式,将其调整到正确的位置。具体步骤如下:
1. 将新元素插入到堆的末尾;
2. 从新元素所在的位置开始,将其与其父节点比较大小,如果比父节点小,则交换两个节点的值,直到新元素大于或等于其父节点,或者到达了堆顶。
代码实现如下:
```python
def min_heap_insert(heap, num):
heap.append(num)
i = len(heap) - 1
while i > 0 and heap[i] < heap[(i-1)//2]:
heap[i], heap[(i-1)//2] = heap[(i-1)//2], heap[i]
i = (i-1) // 2
```
删除堆顶元素时,需要将堆顶元素与堆末尾元素交换,然后将堆末尾元素删除,并从堆顶开始逐步将其与其子节点比较交换的方式,将其调整到正确的位置。具体步骤如下:
1. 将堆顶元素与堆末尾元素交换;
2. 删除堆末尾元素;
3. 从堆顶开始,将其与其子节点比较大小,如果比子节点大,则与其较小的子节点交换,直到找到正确的位置。
代码实现如下:
```python
def min_heap_delete(heap):
if len(heap) == 0:
return None
heap[0], heap[-1] = heap[-1], heap[0]
num = heap.pop()
i, n = 0, len(heap)
while i < n:
left, right = 2*i+1, 2*i+2
if left >= n:
break
if right >= n or heap[left] < heap[right]:
child = left
else:
child = right
if heap[i] > heap[child]:
heap[i], heap[child] = heap[child], heap[i]
i = child
else:
break
return num
```
需要注意的是,这里没有使用哨兵元素,因此在删除堆顶元素时需要判断堆是否为空。
阅读全文