堆

• 堆是一顆完全二叉樹
• 任意節(jié)點(diǎn)的左孩子和右孩子比該節(jié)點(diǎn)值大時(shí)悔醋，是小頂堆
  任意節(jié)點(diǎn)的左孩子和右孩子比該節(jié)點(diǎn)值小時(shí)，是大頂堆
• 堆數(shù)次序是是二叉樹的層次遍歷
• 堆存儲(chǔ)在列表中

堆的操作
①heapify：維護(hù)堆狀態(tài),也叫堆化萄唇。先假設(shè)有了一個(gè)完整的堆蝌戒，當(dāng)根節(jié)點(diǎn)變化時(shí)苟径，需要重新維護(hù)堆狀態(tài)的動(dòng)作。
②build_heap：建堆痛黎，建堆需要從底層建起，找到最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)x刮吧，heapify(x)得到x,x_l_child,x_r_child滿足堆結(jié)構(gòu)湖饱，再找x-1節(jié)點(diǎn)y，heapify(y)得到y(tǒng),y_l_child,y_r_child滿足堆結(jié)構(gòu)杀捻，再找x-2井厌，x-3...逆序遍歷后，每次都是底層堆已經(jīng)完整致讥，只有root節(jié)點(diǎn)不滿足大小仅仆，依次heapify后就完成了建堆操作。時(shí)間復(fù)雜度O(n)
③get_top：取堆頂垢袱，彈出堆頂后墓拜，把堆尾移動(dòng)到堆頂，然后heapify
④insert：插入的數(shù)據(jù)和父節(jié)點(diǎn)比較大小请契，不滿足就交換咳榜，然后遞歸比較。直到滿足條件或到走到堆頂

應(yīng)用場(chǎng)景
topK問題爽锥，優(yōu)先級(jí)隊(duì)列

代碼實(shí)現(xiàn)

class MyHeap(object):
    def __init__(self):
        # i從0開始數(shù),建立大頂堆
        # i從1數(shù),father=i//2;    lchild=i*2;   rchild=i*2+1
        # i從0數(shù),father=(i-1)//2;lchild=i*2+1; rchild=i*2+1+1
        self.data_list = []
        self.top = 0

    def heap_size(self):
        return len(self.data_list) - 1

    def _swap(self, index_a, index_b):
        self.data_list[index_a], self.data_list[index_b] = self.data_list[index_b], self.data_list[index_a]

    def _father(self, i):
        return (i - 1) // 2

    def _lchild(self, i):
        return i * 2 + 1

    def _rchild(self, i):
        return i * 2 + 1 + 1

    # 堆的操作:維護(hù)堆狀態(tài)(堆化),堆的top節(jié)點(diǎn)發(fā)生變化時(shí),重新維護(hù)堆的狀態(tài)
    def heapify(self, root):
        # 如果堆的root不是最大的,那么就和左右孩子中較大的x進(jìn)行交換,然后top改成x涌韩，遞歸堆化，直到?jīng)]有滿足條件或者到底為止
        if root > self.heap_size():
            return
        left_node = self._lchild(root)
        right_node = self._rchild(root)
        largest_node = root

        if left_node <= self.heap_size() and self.data_list[left_node] > self.data_list[largest_node]:
            largest_node = left_node
        if right_node <= self.heap_size() and self.data_list[right_node] > self.data_list[largest_node]:
            largest_node = right_node
        if largest_node != root:
            self._swap(largest_node, root)
            self.heapify(root=largest_node)

    # 堆的操作:建堆氯夷，找到最后一個(gè)node節(jié)點(diǎn)的父節(jié)點(diǎn),然后倒著堆化
    # 因?yàn)榻ǘ咽侵荒軓牡紫峦辖?從上邊之間改堆的節(jié)點(diǎn),堆就會(huì)塌了
    def build_heap(self, data_list):
        self.data_list = data_list
        last_node = self.heap_size()
        last_node_parent = self._father(last_node)
        for i_node in range(last_node_parent, -1, -1):
            self.heapify(i_node)

    # 堆的操作:取堆頂
    def get_heap_top(self):
        if self.heap_size() == 0:
            return None
        res = self.data_list[self.top]
        # 把堆的最后一個(gè)元素和堆頂交換,然后重新堆化
        self.data_list[self.top] = self.data_list.pop()
        self.heapify(self.top)
        return res

    # 堆的操作:插入操作
    def insert(self, data):
        self.data_list.append(data)
        new_data_index = self.heap_size()
        father_index = self._father(new_data_index)
        while self.data_list[father_index] < data and new_data_index != self.top:
            self._swap(father_index, new_data_index)
            new_data_index = father_index
            father_index = self._father(new_data_index)


if __name__ == '__main__':
    data_list = [1, 2, 3, 4, 5, 6, 7]
    s = MyHeap()
    s.build_heap(data_list=data_list)
    print(s.data_list)
    print(s.get_heap_top())
    print(s.get_heap_top())
    print(s.get_heap_top())
    s.insert(data=8)
    print(s.get_heap_top())