数据结构-堆

堆（最小堆）

I 堆化操作

遍历根节点，并且每个根节点都做到下沉。

II 出堆

放出堆顶的元素， 把最后一个元素放到堆顶来下沉。

III 进堆

放入某元素到堆末尾，然后用这末尾的最后一个元素来做上浮操作。

代码

class MyHeap:
    def __init__(self, not_heap):
        self.heap = not_heap[:]
        n = len(self.heap)
        for i in reversed(range(0, (n-1)//2+1)):
            root = i
            while(2*root+1<n):
                leap_small = 2 * root + 1
                if 2 * root + 2 < n and self.heap[2 * root + 2] < self.heap[2 * root + 1]:
                    leap_small = 2 * root + 2
                if self.heap[root] > self.heap[leap_small]:
                    self.heap[root], self.heap[leap_small] = self.heap[leap_small], self.heap[root]
                    root = leap_small
                else:
                    break
        print(self.heap)

    def push(self, n):
        self.heap.append(n)
        i = len(self.heap) - 1
        while(i > 0):
            root = int(str((i - 1) / 2)[:1])
            if self.heap[i] < self.heap[root]:
                leap = self.heap[root]
                self.heap[root] = self.heap[i]
                self.heap[i] = leap
            i = root

    def pop(self):
        result = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        n = len(self.heap)
        root = 0
        while(2 * root + 1 < n):
            leap_small = 2 * root + 1
            if 2 * root + 2 < n and self.heap[2*root+2] < self.heap[2*root+1]:
                leap_small = 2 * root + 2
            if self.heap[root] > self.heap[leap_small]:
                leap = self.heap[root]
                self.heap[root] = self.heap[leap_small]
                self.heap[leap_small] = leap
                root = leap_small
        return result

    def top(self):
        return self.heap[0]

Heapq库

我这个实现的堆结果与常用python库 heapq的结果一致，但是性能未进行比较。常用操作有以下这些:

import heapq
heapq.heapify(list)
heapq.heappush(list, n)
m = heapq.heappop(list)