Python 与二叉堆

hresh 579 0

Python 与二叉堆

什么是二叉堆

二叉堆(binary heap)是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。

构建二叉堆

二叉堆一般用数组来表示。如果根节点在数组中的位置是 1,第 n 个位置的子节点分别在 2n 和 2n+1。因此,第 1 个位置的子节点在 2 和 3,第 2 个位置的子节点在 4 和 5。以此类推。这种基于 1 的数组存储方式便于寻找父节点和子节点。

如果存储数组的下标基于 0,那么下标为i的节点的子节点是 2i + 1 与 2i + 2;其父节点的下标是⌊floor((i − 1) ∕ 2)⌋。函数 floor(x)的功能是“向下取整”,或者说“向下舍入”,即取不大于 x 的最大整数(与“四舍五入”不同,向下取整是直接取按照数轴上最接近要求值的左边值,即不大于要求值的最大的那个值)。比如 floor(1.1)、floor(1.9)都返回 1。

在 Python 中,我们采用列表进行存储二叉堆。

def dowmAjust(num_list: list, parentIndex, lenght):
    '''
    下沉操作,非叶子节点不大于自己的子节点
    :param num_list:
    :param parentIndex:
    :param lenght:
    :return:
    '''
    temp = num_list[parentIndex]
    childrenIndex = parentIndex * 2 + 1
    while childrenIndex < lenght:
        if childrenIndex + 1 < lenght and num_list[childrenIndex + 1] < num_list[childrenIndex]:
            childrenIndex += 1
        if temp <= num_list[childrenIndex]:
            break
        num_list[parentIndex] = num_list[childrenIndex]
        parentIndex = childrenIndex
        childrenIndex = 2 * childrenIndex + 1

    num_list[parentIndex] = temp


def upAdjust(num_list: list, parentIndex, lenght):
    '''
    上浮操作,父节点不小于子节点
    :param num_list:
    :param parentIndex:
    :param lenght:
    :return:
    '''
    temp = num_list[parentIndex]
    childrenIndex = parentIndex * 2 + 1
    while childrenIndex < lenght:
        if childrenIndex + 1 < lenght and num_list[childrenIndex + 1] > num_list[childrenIndex]:
            childrenIndex += 1
        if temp >= num_list[childrenIndex]:
            break
        num_list[parentIndex] = num_list[childrenIndex]
        parentIndex = childrenIndex
        childrenIndex = 2 * childrenIndex + 1

    num_list[parentIndex] = temp

def build_binary_Heap(num_list: list,Flag=True):
    '''
    构建二叉堆
    :param num_list:
    :return:
    '''
    no_leaf_node_index = (len(num_list) - 2) // 2
    while no_leaf_node_index >= 0:
        if Flag:
            dowmAjust(num_list, no_leaf_node_index, len(num_list))#构建最小堆
        else:
            upAdjust(num_list, no_leaf_node_index, len(num_list))#构建最大堆
        no_leaf_node_index -= 1

if __name__ == '__main__':
    num_list = [7, 1, 3, 10, 5, 2, 8, 9, 6]

    build_binary_Heap(num_list,False)
    print(num_list)

插入节点

在数组的最末尾插入新节点。然后自下而上调整子节点与父节点(称作 up-heap 或 bubble-up, percolate-up, sift-up, trickle up, heapify-up, cascade-up 操作):比较当前节点与父节点,不满足“堆性质”则交换。从而使得当前子树满足二叉堆的性质。时间复杂度为 O(log n)。

def addNode(num_list:list, num:int):
    length = len(num_list)
    if length <= 1:
        num_list.append(num)
        print("当前列表仅有两个值,无法判断属于最大堆或最小堆!")
        return

    first_num = num_list[0]
    num_list.append(num)
    parentIndex = ((length+1)-2)//2
    childrenIndex = length
    while childrenIndex > 0:
        if first_num == max(num_list):  #判断该二叉堆是否是最大堆
            if num_list[parentIndex] >= num_list[childrenIndex]:
                break
        elif first_num == min(num_list):  # 判断该二叉堆是否是最小堆
            if num_list[parentIndex] <= num_list[childrenIndex]:
                break
        num_list[childrenIndex],num_list[parentIndex] = num_list[parentIndex],num_list[childrenIndex]
        childrenIndex = parentIndex
        index = (childrenIndex-2)//2
        parentIndex = index if index >=0 else 0

删除节点

删除根节点用于堆排序。

对于最大堆,删除根节点就是删除最大值;对于最小堆,是删除最小值。然后,把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点:对于最大堆,父节点如果小于具有最大值的子节点,则交换二者。这一操作称作 down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max 等。直至当前节点与它的子节点满足“堆性质”为止。

def deleteNode(num_list:list):
    '''
    删除根节点用于堆排序
    对于最大堆,删除根节点就是删除最大值;对于最小堆,是删除最小值。然后,把堆存储的最后那个节点移到填在根节点处。再从上而下调整父节点与它的子节点
    :param num_list:
    :param num:
    :return:
    '''
    length = len(num_list)
    if length <= 1:
        num_list = []

    first_num = num_list[0]
    num_list[0] = num_list[-1]
    num_list.remove(num_list[-1])
    if first_num == max(num_list):  # 判断该二叉堆是否是最大堆
        build_binary_Heap(num_list,False)
    elif first_num == min(num_list):  # 判断该二叉堆是否是最小堆
        build_binary_Heap(num_list)

基础排序

有了堆的基本操作,实现堆的排序就比较简单了,用最大堆实现升序排序。

将最大堆的根节点取出,放入到新的列表中,同时删除该值;把最后一个叶子节点放在根节点的位置,然后对根节点做“上浮”操作,保证根节点为当前所有节点中的最大值。

def heapSort(num_list:list):
    '''
    输入的二叉堆是最大堆,最后输出从小到大的有序集合
    :param num_list:
    :return:
    '''
    sorted_list = []
    length = len(num_list)
    if length <= 1:
        return num_list

    p = -1
    while length-1 > 0:
        sorted_list.insert(0,num_list[0])

        num_list[0],num_list[p] = num_list[p],num_list[0]
        upAdjust(num_list,0,length-1)#上浮操作,保证根节点为当前二叉堆中最大值
        length -= 1
        p -= 1

    return num_list

堆排序分为两步:

  • 将无序列表构建为二叉堆。
  • 循环删除堆顶元素,并将尾部节点移动堆顶,调整堆产生新的堆顶。

堆排序的空间复杂度为 O(1),因为没有开辟额外的集合空间。

计算时间复杂度。因为第一步把无序列表构建成二叉堆,这一步的时间复杂度为 O(n);第二步需要进行 n-1 次循环,每次循环调用一次 upAdjust 方法,所以第二步的计算规模是 (n-1)×logn,时间复杂度为 O(nlogn)。

两个步骤是并列关系,所以整体的时间复杂度是 O(nlogn)。

这里多说几句,堆排序和快速排序相比,有什么区别和联系?

  • 相同点:堆排序和快速排序的平均时间复杂度都是 O(nlogn),都是不稳定排序。
  • 不同点:快速排序的最坏时间复杂度是 O(n^2),而堆排序的最坏时间复杂度稳定在 O(nlogn);此外快速排序和非递归方法的平均空间复杂度都是 O(logn),而堆排序的空间复杂度是 O(1)。

发表评论 取消回复
表情 图片 链接 代码

分享