Python小頂堆的實現

以前都是用的heapq，這次面試碰到讓自己實現一個堆得到top k的元素。拋磚引玉，希望各位提些意見指正

class Heap:def __init__(self, k):self.val = []self.k = kdef get_left(self, idx):return idx * 2 + 1 if len(self.val) > idx * 2 + 1 else Nonedef get_right(self, idx):return idx * 2 + 2 if len(self.val) > idx * 2 + 2 else Nonedef get_parent(self, idx):return (idx - 1) // 2 if idx > 0 else Nonedef sift_up(self, idx):cur = idxparent = self.get_parent(idx)while parent is not None and self.val[cur] < self.val[parent]:# print(parent, cur, self.val[parent], self.val[cur])temp = self.val[cur]self.val[cur] = self.val[parent]self.val[parent] = tempcur = parentparent = self.get_parent(cur)def insert(self, n):if len(self.val) < self.k:self.val.append(n)idx = len(self.val) - 1self.sift_up(idx)else:if n > self.val[0]:self.delete()self.val.append(n)idx = len(self.val) - 1self.sift_up(idx)returndef sift_down(self, idx):l = self.get_left(idx)r = self.get_right(idx)cur = idxif not l:min_child = relif not r:min_child = lelse:min_child = l if self.val[l] == min(self.val[l], self.val[r]) else rwhile cur is not None and min_child is not None and self.val[cur] > self.val[min_child]:# print(cur, min_child, self.val[cur], self.val[min_child])temp = self.val[cur]self.val[cur] = self.val[min_child]self.val[min_child] = tempcur = min_childl = self.get_left(cur)r = self.get_right(cur)if not l:min_child = relif not r:min_child = lelse:min_child = l if self.val[l] == min(self.val[l], self.val[r]) else rdef delete(self):if self.val:temp = self.val[0]self.val[0] = self.val[-1]self.val[-1] = tempn = self.val.pop()self.sift_down(0)return nreturn None

總結

以上是生活随笔為你收集整理的Python小顶堆的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。