二叉堆(Binary Heap)

二叉堆这个数据结构有点意思，自己做了个总结，内容结构如下：

• 二叉堆性质

• 二叉堆操作

• 应用

二叉堆性质：

堆（Heap）是一个可以被看成近似完全二叉树的结构，具有完全二叉树的特性：

• 缺少的叶子节点总是位于右子节点
• n个节点的完全二叉树高度：k=⌊ log2ⁿ⌋（向上取整）
• 从1开始按层序编号，那么第i个节点有如下性质：
  1. 其左子节点索引是：2i
  2. 其又子节点索引是：2i+1
  3. 其父节点索引为 ： i // 2

同时具有堆的特性：

• 堆顶元素就是最值，O(1)时间就能优先拿到
• 从根节点（堆顶）到堆中每一个节点都是一个有序序列。

• 存储方式可以用线性的数组来实现，实现简单易操作，不过要注意数组下标从0开始，这个位置预留占位，节点的索引从1开始编号。

  
  2.png

binarytree.png

二叉堆操作：

• BinaryHeap()：创建一个空的二叉堆对象
• insert(key)：将新元素加入到堆中
• findMin()：返回堆中的最小项，最小项仍保留在堆中
• delMin()：返回堆中的最小项，同时从堆中删除
• isEmpty()：返回堆是否为空
• size()：返回堆中节点的个数
• buildHeap(lst)：从一个包含节点的列表里创建新堆

# 直接导入Pythonds包使用其提供的有关堆的数据结构。
from pythonds.trees import BinaryHeap
bheap=BinaryHeap()
bheap.insert(5)

#用list来实现对堆的操作
class BinaryHeap(object):
    """定义一个二叉堆"""

    def __init__(self):
        self.heapList = [0]  # 第一个堆元素从1开始编号，索引为0占位不用
        self.currentSize = 0

    def percolateUP(self, i):
        '''将第i个元素上浮到合适位置'''
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                self.heapList[i], self.heapList[
                    i // 2] = self.heapList[i // 2], self.heapList[i]
            else:
                break
            i = i // 2

    def percolateDown(self, i):
        '''将第i个元素下沉到合适位置'''
        while (2 * i) <= self.currentSize:
            minIndex = self.minChild(i)
            if self.heapList[i] > self.heapList[minIndex]:
                self.heapList[i], self.heapList[
                    minIndex] = self.heapList[minIndex], self.heapList[i]
            else:
                break
            i = minIndex

    def minChild(self, i):
        '''返回第i个元素左右子节点中最小值'''
        if (2 * i + 1) > self.currentSize:
            return 2 * i  # 只有一个子节点（左子节点）
        elif self.heapList[2 * i] < self.heapList[2 * i + 1]:
            return 2 * i
        else:
            return 2 * i + 1

    def insert(self, key):
        '''将新元素加入到堆中'''
        self.heapList.append(key)
        self.currentSize = self.currentSize + 1
        self.percolateUP(self.currentSize)  # 新值上浮

    def findMin(self):
        '''返回堆中的最小项，最小项仍保留在堆中'''
        return heapList[1]

    def delMin(self):
        '''返回堆中的最小项，同时从堆中删除'''
        result = self.heapList[1]
        # 将最后一个元素换到堆顶并删除堆顶元素
        self.heapList[1] = self.heapList.pop()
        self.currentSize = self.currentSize - 1
        self.percolateDown(1)  # 将堆顶元素下沉
        return result

    def isEmpty(self):
        '''返回堆是否为空'''
        return len(heapList) == 1

    def size(self):
        '''返回堆中节点的个数'''
        return len(heapList) - 1

    def printHeap(self):
        print(self.heapList[1:])

    def buildHeap(self, lst):
        '''从一个包含节点的列表里创建新堆,用下沉法将时间复杂度控制在O(n)'''
        self.currentSize = len(lst)
        i = self.currentSize // 2 #从最后一个节点的父节点开始过滤下沉！
        self.heapList = [0] + lst[:]
        while i > 0:
            self.percolateDown(i)
            i = i - 1
        self.printHeap()

应用之一-----------------优先队列：

可以在O(1)时间拿到最值，获取最优解，实现对VIP或者进程的优先级等操作 pic_19.png

应用之二-----------------堆排序：