heap (堆)

堆: 说实话在仔细研究堆之前，我一直将它跟堆栈混为了一个东西。还想着这是一个后进先出的东西。
我们来看一下什么是堆:
计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
再来看一下堆得定义(核心):

n个元素序列{k1, k2... ki...kn},当且仅当满足下列关系时称之为堆：
(ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1), (i = 1, 2, 3, 4... n/2)

堆两大使用:

1. 更多用于动态数据的维护
2. 提取前M个元素

生成一个堆

class HeapHeap(object):
    def __init__(self, size):
        self._heap = [0] * (size + 1)
        self._heap_count = 0

添加元素

    def insert_element(self, element):
        if self._heap_count == 0:
            #这里需要说一下，我们的堆是从数组第一个位置开始的so这里第一个元素为self._heap[1] = element
            self._heap[1] = element
            self._heap_count += 1
            return
        if self._heap_count == len(self._heap):
            return

        self._heap_count += 1
        self._heap[self._heap_count] = element
        self.reset_heap_up(self._heap_count)
    
    #这里我使用的是递归(自从快速排序那里用递归后，对递归很向往，于是这里也用了递归)
    def reset_heap_up(self, index):
        #这里使用index > 1来控制结束是因为index // 2有可能会是0，这样就不满足条件了
        if self._heap[index] > self._heap[index // 2] and index > 1:
            self._heap[index], self._heap[index // 2] = self._heap[index // 2], self._heap[index]
            self.reset_heap_up(index // 2)
        else:
            return

删除元素

    def remove_element(self):
        self._heap[1] = self._heap[self._heap_count]
        return_num = self._heap[self._heap_count]
        self._heap[self._heap_count] = -1
        self._heap_count -= 1
        self.reset_heap_down(1)
        return return_num
    
    #这里的思路是 将第一个元素与末尾元素交换，然后再将其转换为堆
    def reset_heap_down(self, index):
        j = index * 2  
        #确保不越界
        if j <= self._heap_count:
            #确保不越界，如果j + 1 < self._heap_count 说明有右孩子，这是比较两个孩子的大小，择大与父元素交换
            if j + 1 <= self._heap_count:
                change_index = j if self._heap[j] > self._heap[j + 1] else (j + 1)
            else:
                change_index = j
            #同时保证交换的孩子元素 > 父元素
            if self._heap[change_index] > self._heap[index]:
                self._heap[index], self._heap[change_index] = self._heap[change_index], self._heap[index]
            self.reset_heap_down(change_index)
        else:
            return

堆排序

    #根据堆的根元素肯定会是堆里面最大的元素，同时在数组中是第一个元素这一特性来进行排序
    def sort_heap(self):
        if self._heap_count == 1:
            return
        #将第一个跟最后一个元素交换，这样最后一个就成了最大值
        self._heap[self._heap_count], self._heap[1] = self._heap[1], self._heap[self._heap_count]
        #改变_heap_count避免再次堆化的时候重复执行
        self._heap_count -= 1
        #重新堆化
        self.reset_heap_down(1)
        self.sort_heap()