堆

堆排序

堆排序是利用堆进行排序的
堆是一种完全二叉树
堆有两种形式:大根堆和小根堆
大根堆：每个节点的值都大于或等于左右孩子节点
小根堆:每个节点的值都小于或等于左右孩子节点

如果给大小根堆的根节点从1开始编号,则满足下面关系

左侧的是小根堆,右侧是大根堆

堆的特点:这种结构处于一种半排序状态,它的存取效率从整体上讲介于有序和无序之间.当对象处于动态时,是种非常有优势的数据结构.存取的时间复杂度为log(a,n),其中a为完全树的度。

二叉堆存储以及规律:通常二叉堆以数组存储,且父子节点的下标存在如下关系:父节点(下标为i)的左孩子节点下标为2i,右孩子下标为(2i+1),另外堆顶元素的下标为1,层为log(2,n).注:这里下标是从1开始的.

堆排序思路:对于一个堆(以下皆以二叉最小堆说明),去掉它的堆顶元素,然后以最末端元素移动到堆顶位置,然后进行调整,使之再次成为最小堆.如此迭代,知道没有剩余的元素。

建堆思路:从最后一个非叶子节点开始,按照从下到上的顺序进行迭代,让它(下标记为x)同其孩子节点(下标:2x、2x+1)比较,如果满足小于任何一个孩子节点,则说明这个子树是符合堆规则的;否则把其他同其最小的子节点交换。优于交换后,以这个节点(x)会破坏原来孩子的堆特性,因此这里有一个子迭代,让他继续上面的行为,知道找到一个合适的位置落脚.如此,直到根节点,就可以保证整棵完全树具备堆的性质.具体见图片,这里描述的是大根堆的建堆过程,小根堆类似.

算法三围

时间复杂度

建堆需要的时间:O(n)
取堆顶元素并调整需要的时间:O(nlog(2,n))
最坏情况:同平均复杂度
最好情况:O(1)

空间复杂度

O(1),用来交换的临时空间。建堆过程不需要额外的空间

稳定性

相同的关键字的2个元素有可能并不是同一个父节点,因此保证不了其稳定性.
(稳定性对于多个关键词的排序很有用,如果不稳定就不能直接应用于多个关键词的排序了)

算法的应用

堆最常用于优先队列以及相关动态问题

优先队列

优先队列指的是元素入队和出队的顺序和时间无关,既不是先进先出,也不是先进后出,而是根据元素的重要性来决定的.

优先队列是一种抽象的数据类型，它和堆的关系类似于，List和数组、链表的关系一样；我们常常使用堆来实现优先队列，因此很多时候堆和优先队列都很相似，它们只是概念上的区分。
优先队列的应用场景十分的广泛：
常见的应用有：

Dijkstra’s algorithm（单源最短路问题中需要在邻接表中找到某一点的最短邻接边，这可以将复杂度降低。）
Huffman coding（贪心算法的一个典型例子，采用优先队列构建最优的前缀编码树(prefixEncodeTree)）
Prim’s algorithm for minimum spanning tree
Best-first search algorithms

python实现堆

懒人方法

heapq模块
首先明确，heapq模块是可以用来求前n个最大/最小值的
通常在Python中，求前n个最大/最小值的方法无非是通过排序，它通常和列表相联系

lyst = [-3, 22, 45, 34, 99, 102, -44]

low3 = sorted(lyst)[:3]
top3 = sorted(lyst, reverse=True)[:3]

import heapq

lyst = [-3, 22, 45, 34, 99, 102, -44]

low3 = heapq.nlargest(3, lyst)
top3 = heapq.nsmallest(3, lyst)

heapq.nlargest()可以带key参数

items=[{'item':'apple','price':10},
       {'item':'banana','price':12},
       {'item':'water','price':1}]
top2=heapq.nlargest(2,items,key=lambda s:s['price'])

python的heapq默认是小根堆
heappush(treelist,item)将新元素添加heaplist列表中

lyst=[6,9,7,2,4,3,6]
heaptree=[]
for item in lyst:
  heapq.heappush(heaptree,item)

heappop(heap)每次从heap堆中弹出堆顶元素

1
2
3

lyst=[6,9,7,2,4,3,6]
while lyst:
  heapq.heappop(lyst)

heappushpop(heap, item)等于先push(heap, item)再heappop(heap)，但是比分别调用二者要快

heapreplace(heap, item)等于先heappop(heap)再heappush(heap, item)，但是比分别调用二者要快

heapify(treelist)：将列表treelist进行堆调整，默认的是小根堆

heapq.merge(* heap)：将多个列表合并，并进行堆调整，返回的是合并后的列表的迭代器

劳动人民方法

(1)大根堆调整(max_heapify)
将堆的末端子节点做调整,使其永远小于父节点.
比较i的根节点和与其所对应i的孩子节点的值,当i根节点的值比左孩子节点的值要小的时候,就把i根节点和左孩子节点所对应的值进行交换.同理.

def max_heapify(heap,heapSize,root):  # 调整列表中的元素并保证以root为根的堆是一个大根堆
    '''
    给定某个节点的下标root，这个节点的父节点、左子节点、右子节点的下标都可以被计算出来。
    父节点：(root-1)//2
    左子节点：2*root + 1
    右子节点：2*root + 2  即：左子节点 + 1
    '''
    left = 2*root + 1
    right = left + 1
    larger = root
    if left < heapSize and heap[larger] < heap[left]:
        larger = left
    if right < heapSize and heap[larger] < heap[right]:
        larger = right
    if larger != root:  # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作
        heap[larger], heap[root] = heap[root], heap[larger]
        # 递归的对子树做调整
        max_heapify(heap, heapSize, larger)

(2)建立大根堆
将堆中所有的数据重新排序。建堆的过程其实就是不断做大根堆调整的过程，从(heapSize -2)//2处开始调整，一直调整到第一个根节点。

def build_max_heap(heap):  # 构造一个堆，将堆中所有数据重新排序
    heapSize = len(heap)
    for i in range((heapSize -2)//2,-1,-1):  # 自底向上建堆
        max_heapify(heap, heapSize, i)

(3)堆排序(heap_sort)：
将根节点取出与最后一位做对调，并做最大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。
首先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面len(heap)-1个节点继续做堆调整，直到将所有的节点取出，对于有n个元素的一维数组我们只需要做n-1次操作。(堆排序只能确定根节点是最大的或是最小的)

import random

def heap_sort(heap):  # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
    build_max_heap(heap)
    # 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
    for i in range(len(heap)-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heapify(heap, i, 0)

# 测试
if __name__ == '__main__':
    a = [30, 50, 57, 77, 62, 78, 94, 80, 84]
    print(a)
    heap_sort(a)
    print(a)
    b = [random.randint(1,1000) for i in range(1000)]
    print(b)
    heap_sort(b)
    print(b)

笔试刷题（二）

堆

堆排序