这是我对在Python中使用筛选实现最小堆的看法。
有没有办法缩短筛选代码?我试着不使用那么多if子句,但我似乎无法将其缩短。
import math
class MinHeap:
def __init__(self, arr):
self.arr = arr
self.n = len(arr)
def heapify(self):
depth = int(math.log2(self.n))
for i in range((2 ** depth) - 2, -1, -1):
self.sift_down(i)
def sift_down(self, i):
while (2 * i) + 1 < self.n or (2 * i) + 2 < self.n:
i = self.sift_down_level(i)
def sift_down_level(self, i):
left_smaller = right_smaller = False
if self.is_left_child_exists(i) and self.arr[(2 * i) + 1] < self.arr[i]:
left_smaller = True
if self.is_right_child_exists(i) and self.arr[(2 * i) + 2] < self.arr[i]:
right_smaller = True
if left_smaller and right_smaller:
if self.arr[(2 * i) + 1] < self.arr[(2 * i) + 2]:
self.arr[(2 * i) + 1], self.arr[i] = self.arr[i], self.arr[(2 * i) + 1]
return (2 * i) + 1
else:
self.arr[(2 * i) + 2], self.arr[i] = self.arr[i], self.arr[(2 * i) + 2]
return (2 * i) + 2
elif left_smaller:
self.arr[(2 * i) + 1], self.arr[i] = self.arr[i], self.arr[(2 * i) + 1]
return (2 * i) + 1
elif right_smaller:
self.arr[(2 * i) + 2], self.arr[i] = self.arr[i], self.arr[(2 * i) + 2]
return (2 * i) + 2
return -1
def is_left_child_exists(self, i):
if (2 * i) + 1 < self.n:
return True
return False
def is_right_child_exists(self, i):
if (2 * i) + 2 < self.n:
return True
return False
nums = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
heap = MinHeap(nums)
heap.heapify()
