什么是堆

堆是一个数组,它可以被看成是一个近似的二叉树
image.png

堆是从左向右填充的,除了最底层,该树是被完全填充的,给定一个节点i,我们可以很容易计算出他的父节点,左孩子和右孩子.

不同语言的实现方式是不一样的,在python中的实现如下:

def parent(i):
    return int(i/2)

def left(i):
    return 2*i+1

def right(i):
    return 2*(i+1)

堆有两种形式:最大堆和最小堆.最大堆指父节点大于等于子节点的堆,最小堆指父节点小于等于子节点的堆.由此可知,最大堆中最大的元素在根节点,最小堆中最小的元素在根节点.

对于特定的应用来说,必须指明是最大堆还是最小堆;而当应用即使用与最大堆也适用于最小堆时,我们称之为"堆".

维护堆的性质

在下图(a)中,只有i节点是不满足最大堆父节点必须大于子节点这一性质的.我们现在需要修复它.
image.png
找出i节点与i节点的左右子节点中最大的,i节点与最大节点交换,如图(b).但这是又会导致下面的树不满足最大堆的性质,所以需要递归的维护堆的性质.

def max_heapify(A,i,length = None):
    l = left(i)
    r = right(i)
    if length == None:
        length = len(A)
        
    if l < length and A[l] > A[i]:
        largest = l
    else:
        largest = i
        
    if r < length and A[r] > A[largest]:
        largest = r

    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        max_heapify(A,largest,length)
A = [16,4,10,14,7,9,3,2,8,1]
max_heapify(A,1)
print(A)   # [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

建堆

建堆是将一个数组转换成一个堆的过程.数组可以看成是一个完全不满足堆性质的二叉树,我们只需自底向上运用max_heapify()函数维护每一个节点的性质即可.若2叉数节点个数为n,则最底层节点为n/2,我们只需维护非最底层的节点:

def build_max_heap(A):
    for i in range(int(len(A)/2))[::-1]:
        max_heapify(A,i)

堆排序算法

因为最大堆的根节点一定是最大值,所以我们每次取出根节点,选择一个根节点的孩子节点作为根节点,这样就可以从大到小取出所有的数据.

image.png

def heapsort(A):
    build_max_heap(A)
    for i in range(1,len(A))[::-1]:
        tmp = A[i]
        A[i] = A[0]
        A[0] = tmp
        max_heapify(A,0,i)
A = [16,4,10,14,7,9,3,2,8,1]
heapsort(A)
print(A)   # [16, 14, 10, 9, 8, 7, 4, 3, 2, 1]

堆排序算法的复杂度为O ( n \lg n ),函数build_max_heap()的复杂度是O(n),函数max_heapify()的复杂度是O(\lg n),所以总的复杂度为O(n) + (n-1)O(\lg n) = O(n\lg n)

优先队列

优先队列是一种用来维护由一组元素构成的集合S的数据结构,随时有数据被加入进集合,每次我们取集合中最大或最小的数进行处理,对应称之为最大优先队列与最小优先队列.

最粗暴的方法是每次取数据的时候先进行排序,这样可以保证取到最大值.但是每次都进行排序显然时间复杂度会非常高.我们可以用堆来解决这个问题.

class heapq():
    def __init__(self,A):
        self.A = A
        for i in range(int(len(self.A)/2))[::-1]:
            self.max_heapify(self.A,i)
            
    def parent(self,i):
        return int(i/2)
    
    def left(self,i):
        return 2*i+1

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

    def max_heapify(self,A,i,length = None):
        l = self.left(i)
        r = self.right(i)
        if length == None:
            length = len(A)

        if l < length and A[l] > A[i]:
            largest = l
        elif r < length and A[r] > A[i]:
            largest = r
        else:
            largest = i

        if largest != i:
            tmp = A[i]
            A[i] = A[largest]
            A[largest] = tmp
            self.max_heapify(A,largest,length)
    
    # 返回最大的元素
    def heap_maximum(self):
        return self.A[0]
    
    # 返回最大的元素,并去掉最大的元素
    def heap_extract_max(self):
        m = self.A[0]
        A[0] = A[len(self.A)-1]
        del A[len(self.A)-1]
        self.max_heapify(self.A,0)
        return m
    
    def heap_increase_key(self,A,i):
        while A[self.parent(i)] < A[i]:
            tmp = A[i]
            A[i] = A[self.parent(i)]
            A[self.parent(i)] = tmp
            i = self.parent(i)
            
    # 插入元素x
    def insert(self,x):
        self.A.append(x)
        self.heap_increase_key(self.A,len(self.A)-1)
        
A = [16,4,10,14,7,9,3,2,8,1]
q = heapq(A)
print(q.heap_extract_max())
print(q.heap_extract_max())
q.insert(13)
q.insert(15)
print(q.heap_extract_max())
q.insert(5)
print(q.heap_extract_max())
print(q.heap_extract_max())


# output : 
16
14
15
13
10
posted @ 2019-02-06 16:04:10
评论加载中...

发表评论