| 1 | # 构建树实现堆 |
| 2 | class BinHeap: |
| 3 | def __init__(self): |
| 4 | self.heapList = [0] |
| 5 | self.currentSize = 0 |
| 6 | |
| 7 | #插入新结点后必要时交换子节点和父节点的位置保持堆的性质 |
| 8 | def percUp(self, i): |
| 9 | while i//2 > 0: |
| 10 | if self.heapList[i] < self.heapList[i//2]: |
| 11 | temp = self.heapList[i//2] |
| 12 | self.heapList[i//2] = self.heapList[i] |
| 13 | self.heapList[i] = temp |
| 14 | i = i//2 |
| 15 | |
| 16 | # 插入节点 |
| 17 | def insert(self, k): |
| 18 | self.heapList.append(k) |
| 19 | self.currentSize += 1 |
| 20 | self.percUp(self.currentSize) |
| 21 | |
| 22 | # 删除堆顶元素后, 交换堆尾和空堆顶的位置并实现元素的下沉 |
| 23 | def percDown(self, i): |
| 24 | while (i*2) <= self.currentSize: |
| 25 | mc = self.minChild(i) |
| 26 | if self.heapList[i] > self.heapList[mc]: |
| 27 | temp = self.heapList[i] |
| 28 | self.heapList[i] = self.heapList[mc] |
| 29 | self.heapList[mc] = temp |
| 30 | i = mc |
| 31 | |
| 32 | def minChild(self, i): |
| 33 | if i * 2 + 1 > self.currentSize: |
| 34 | return i * 2 |
| 35 | else: |
| 36 | if self.heapList[i*2] < self.heapList[i*2+1]: |
| 37 | return i * 2 |
| 38 | else: |
| 39 | return i * 2 + 1 |
| 40 | |
| 41 | def delMin(self): |
| 42 | retval = self.heapList[1] |
| 43 | self.heapList[1] = self.heapList[self.currentSize] |
| 44 | self.currentSize = self.currentSize - 1 |
| 45 | self.heapList.pop() |
| 46 | self.percDown(1) |
| 47 | return retval |
| 48 | |
| 49 | def buildHeap(self, alist): |
| 50 | i = len(alist) // 2 |
| 51 | self.currentSize = len(alist) |
| 52 | self.heapList = [0] + alist[:] |
| 53 | while (i > 0): |
| 54 | self.percDown(i) |
| 55 | i = i - 1 |
| 56 | return self.heapList |
| 57 | |
| 58 | H = BinHeap() |
| 59 | print(H.buildHeap([9, 6, 5, 2, 3])) |