精华内容
下载资源
问答
  • 采用自底向上方式构建二叉的理论分析、Python实现以及O(n)最坏时间复杂度分析

    在文章【数据结构Python描述】树堆(heap)简介和Python手工实现及使用树堆实现优先级队列中,为了能对优先级队列中键值对的增删都较为高效,我们基于二叉堆实现了HeapPriorityQueue

    对于使用HeapPriorityQueue创建的对象q,其中用于保存优先级队列键值对的二叉堆初始为空,如后续需要通过优先级队列操作的键值对数量为 n n n,虽然我们大可以重复调用 n n n次对象qadd(k, v)方法构建堆,但是根据文章【常见算法Python描述】优先级队列应用之实现选择排序、插入排序和堆排序分析,该操作的最坏时间复杂度为 n l o g ( n ) nlog(n) nlog(n)

    如果 n n n对键值对提前给定,如【常见算法Python描述】优先级队列应用之实现选择排序、插入排序和堆排序中具有 n n n个元素的待排序集合,此时就可通过本文下面将介绍的自底向上(Bottom-Up)方式构建二叉堆,这种方式的最坏时间复杂度为 O ( n ) O(n) O(n)

    一、堆数据结构创建

    为描述方便,下面介绍自底向上构建堆的方式时,假设给定数量为 n = 2 h + 1 − 1 n=2^{h+1}-1 n=2h+11(其中 h h h为堆的高度)的任意顺序键值对,则数量为 n n n的键值对恰好可以填满高度为 h h h完全二叉树,且每一层的键值对数量分别为 1 1 1 2 1 2^1 21 2 2 2^2 22 ⋅ ⋅ ⋅ \cdot\cdot\cdot 2 h − 1 2^{h-1} 2h1 2 h {2^h} 2h,此时二叉树的高度为 h = l o g ( n + 1 ) − 1 h=log(n+1)-1 h=log(n+1)1

    1. 建堆步骤

    下面以给定 n = 15 n=15 n=15个键值对为例介绍如何自底向上构建堆:

    在这里插入图片描述

    易知,上述 n = 15 n=15 n=15个键值对可以填满高度为 h = l o g ( 16 ) − 1 = 3 h=log(16)-1=3 h=log(16)1=3完全二叉树(但根据堆的定义,此时完全二叉树还不是堆),如下图(a)所示:

    在这里插入图片描述

    下面的图(b)至图(h)介绍了具体的建堆过程:

    • 第一步(如图(b)所示),构建 ( 15 + 1 ) / 2 1 = 8 (15+1)/{2^1}=8 (15+1)/21=8个仅有一个键值对的堆:

    在这里插入图片描述

    • 第二步
      • 首先如图(c)所示,构建 ( 15 + 1 ) / 2 2 = 4 (15+1)/{2^2}=4 (15+1)/22=4个完全二叉树,每个包含 3 3 3个键值对;
      • 然后如图(d)所示,因为每个完全二叉树都可能违背堆序性质,因此可能需要进行父子结点间键值对的交换,最后才能得到 4 4 4

    在这里插入图片描述

    • 第三步
      • 首先如图(e)所示,构建 ( 15 + 1 ) / 2 3 = 2 (15+1)/{2^3}=2 (15+1)/23=2完全二叉树,每个包含 7 7 7个键值对;
      • 然后如图(f)所示,因为每个完全二叉树都可能违背堆序性质,因此可能需要进行父子结点间键值对的交换,最后才能得到 2 2 2

    在这里插入图片描述

    • 第四步
      • 首先如图(g)所示,构建 ( 15 + 1 ) / 2 4 = 1 (15+1)/{2^4}=1 (15+1)/24=1完全二叉树,其中包含 15 15 15个键值对;
      • 然后如图(h)所示,因为该完全二叉树都可能违背堆序性质,因此可能需要进行父子结点间键值对的交换,最后才能得到根据给定的 15 15 15个键值对需构建的 1 1 1二叉堆

    在这里插入图片描述

    2. 建堆实现

    分析上述建堆过程可知,实现建堆最重要的是如何将两个形态和大小完全相同的子堆在根结点处进行合并,且保证合并后得到的完全二叉树是一个二叉堆

    实际上,对于以列表方式给出键值对形式结点元素的完全二叉树,文章【数据结构Python描述】树堆(heap)简介和Python手工实现及使用树堆实现优先级队列中介绍的自堆顶向下冒泡算法实现_downheap()恰好可以满足该需求。

    具体地,在实现上述建堆过程时,只需要对完全二叉树从最底层最右侧结点开始直到根结点的每一个结点使用一个循环,依次调用_downheap()方法即可。

    更进一步地,因为_downheap()方法不对叶子结点执行任何操作,所以上述循环只需从最底层的非叶子结点开始依次调用_downheap()方法

    对上述分析使用Python实现如下:

    def __init__(self, contents=tuple()):
        """
        初始化一个优先级队列
        默认将新创建的优先级队列初始化为空,如果提前给定元素为(k, v)形式的contents集合,则使用contents初始化优先级队列
        :param contents:(k, v)形式元素contents集合
        """
        self._data = [self._Item(k, v) for k, v in contents]
        if len(self._data) > 1:
            self._heapify()
    
    def _heapify(self):
        """
        具体执行自底向上建堆
        :return: None
        """
        start = self._parent(len(self) - 1)  # 从最后一个叶子结点的父结点开始
        for j in range(start, -1, -1):  # 自底向上
            self._downheap(j)
    

    分析上述代码可知,建堆实现只是将HeapPriorityQueue__init__()方法进行了重新设计并提供了一个非公有的实用方法_heapify(),其逻辑为:在使用HeapPriorityQueue创建对象时,其初始化方法接收一个可选参数contents,该参数是元素为(k, v)形式的元组,与旧的初始化方法不同的是,这里使用列表推导式初始化后续建堆用的列表。

    3. 建堆效率

    为了分析自底向上建堆的实现_heapify()方法的时间复杂度,这里:

    • 首先给出结论:

    针对提前给定的 n n n个键值对,如采用自底向上的方式构建堆,则假定键值对间两两比较的时间复杂度为 O ( 1 ) O(1) O(1),则该建堆方式的最坏时间复杂度为 O ( n ) O(n) O(n)

    • 然后以上述给定的 15 15 15个键值对为例进行验证;
    • 最后再进行一般性分析。

    对于给定具有任意顺序的 15 15 15个键值对

    _heapify()中,最坏情况下,循环每一次迭代的运行时间正比于当前结点到最底层结点(此处为第 4 4 4层结点)的高度,因此:

    • 4 4 4层结点数量为 2 3 = 8 2^{3}=8 23=8,但是_heapify()不对这些结点执行任何操作,因此本层的时间复杂度为 0 0 0
    • 3 3 3层结点数量为 2 2 = 4 2^{2}=4 22=4,当前所有结点到最底层结点(此处为第 4 4 4层结点)的高度 1 1 1,则对该层每个结点调用_downheap()的最坏时间复杂度正比于 4 × 1 = 4 4\times1=4 4×1=4
    • 2 2 2层结点数量为 2 1 = 2 2^{1}=2 21=2,当前所有结点到最底层结点(此处为第 4 4 4层结点)的高度 2 2 2,则对该层每个结点调用_downheap()的最坏时间复杂度正比于 2 × 2 = 4 2\times2=4 2×2=4
    • 1 1 1层结点数量为 2 0 = 1 2^{0}=1 20=1,当前所有结点到最底层结点(此处为第 4 4 4层结点)的高度 3 3 3,则对该层每个结点调用_downheap()的最坏时间复杂度正比于 1 × 3 = 3 1\times3=3 1×3=3

    综上,即_heapify()的最坏时间复杂度正比于 4 + 4 + 3 = 11 < 15 4+4+3=11<15 4+4+3=11<15

    一般地,对于给定具有任意顺序的 n = 2 h + 1 − 1 n=2^{h+1}-1 n=2h+11个键值对

    • h h h层结点数量为 2 h 2^h 2h,但是_heapify()不对这些结点执行任何操作,因此本层的时间复杂度为 0 0 0
    • h − 1 h-1 h1层结点数量为 2 h − 1 2^{h-1} 2h1,当前所有结点到的高度 1 1 1,则对该层每个结点调用_downheap()的最坏时间复杂度正比于 2 h − 1 × 1 {2^{h-1}}\times1 2h1×1
    • h − 2 h-2 h2层结点数量为 2 h − 2 2^{h-2} 2h2,当前所有结点到的高度 2 2 2,则对该层每个结点调用_downheap()的最坏时间复杂度正比于 2 h − 2 × 2 {2^{h-2}}\times2 2h2×2
    • ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ \cdot\cdot\cdot\cdot\cdot\cdot
    • h − j h-j hj层结点数量为 2 h − j 2^{h-j} 2hj,当前所有结点到的高度 j j j,则对该层每个结点调用_downheap()的最坏时间复杂度正比于 2 h − j × j {2^{h-j}}\times{j} 2hj×j
    • ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ \cdot\cdot\cdot\cdot\cdot\cdot
    • 0 0 0层结点数量为 2 0 2^{0} 20,当前所有结点到的高度 h h h,则对该层每个结点调用_downheap()的最坏时间复杂度正比于 2 0 × h {2^{0}}\times{h} 20×h

    因此,总的建堆时间复杂度正比于:

    f ( n ) = ∑ j = 0 h j 2 h − j f(n)=\sum\nolimits_{j=0}^{h}{j}{2^{h-j}} f(n)=j=0hj2hj

    变形后得:

    f ( n ) = 2 h ∑ j = 0 h j 2 j f(n)={2^h}\sum\nolimits_{j=0}^{h}{\frac{j}{2^j}} f(n)=2hj=0h2jj

    因此,重点是求下列表达式的和:

    ∑ j = 0 h j 2 j \sum\nolimits_{j=0}^{h}{\frac{j}{2^j}} j=0h2jj

    为了求出上述表达式的和,需要使用下面的数学技巧:

    • 首先,根据高中数学知识,对任意 x < 1 x\lt1 x<1,有下列等比数列求和公式:

    ∑ j = 0 ∞ x j = 1 1 − x \sum\nolimits_{j=0}^{\infty}{x^j}=\frac{1}{1-x} j=0xj=1x1

    • 然后,上述等式两端对 x x x求导后得:

    ∑ j = 0 ∞ j x j − 1 = 1 ( 1 − x ) 2 \sum\nolimits_{j=0}^{\infty}{j}{x^{j-1}}=\frac{1}{(1-x)^2} j=0jxj1=(1x)21

    上式两边同乘以 x x x后得:

    ∑ j = 0 ∞ j x j = x ( 1 − x ) 2 \sum\nolimits_{j=0}^{\infty}{j}{x^{j}}=\frac{x}{(1-x)^2} j=0jxj=(1x)2x

    • 最后,如果令上述等式 x = 1 / 2 x={\left.1\middle/2\right.} x=1/2,则:

    ∑ j = 0 ∞ j 2 j = 1 / 2 ( 1 − ( 1 / 2 ) ) 2 = 2 \sum\nolimits_{j=0}^{\infty}\frac{j}{2^j}=\frac{{\left.1\middle/2\right.}}{(1-({\left.1\middle/2\right.}))^2}=2 j=02jj=(1(1/2))21/2=2

    因此:

    f ( n ) = 2 h ∑ j = 0 h j 2 j < 2 h ∑ j = 0 ∞ j 2 j = 2 h × 2 = 2 h + 1 f(n)={2^h}\sum\nolimits_{j=0}^{h}{\frac{j}{2^j}}\lt{{2^h}\sum\nolimits_{j=0}^{\infty}{\frac{j}{2^j}}}=2^h\times{2}=2^{h+1} f(n)=2hj=0h2jj<2hj=02jj=2h×2=2h+1

    又本节开头假定 n = 2 h + 1 − 1 n=2^{h+1}-1 n=2h+11,于是 f ( n ) < n + 1 ∈ O ( n ) f(n)\lt{n+1}\in{O(n)} f(n)<n+1O(n)。至此,证毕。

    二、完整测试代码

    下面是针对【数据结构Python描述】树堆(heap)简介和Python手工实现及使用树堆实现优先级队列中实现的HeapPriorityQueue,使用自底向上建堆方法完善后得到的最终结果及其测试代码:

    # heap_priority_queue.py
    from priority_queue import PriorityQueueBase
    
    
    class Empty(Exception):
        """尝试对空优先级队列进行删除操作时抛出的异常"""
        pass
    
    
    class HeapPriorityQueue(PriorityQueueBase):
        """使用堆存储键值对形式记录的优先级队列"""
    
        def __init__(self, contents=tuple()):
            """
            初始化一个优先级队列
            默认将新创建的优先级队列初始化为空,如果提前给定元素为(k, v)形式的contents集合,则使用contents初始化优先级队列
            :param contents:(k, v)形式元素contents集合
            """
            self._data = [self._Item(k, v) for k, v in contents]
            if len(self._data) > 1:
                self._heapify()
    
        def _heapify(self):
            """
            具体执行自底向上建堆
            :return: None
            """
            start = self._parent(len(self) - 1)  # 从最后一个叶子结点的父结点开始
            for j in range(start, -1, -1):  # 自底向上
                self._downheap(j)
    
        def _parent(self, j):
            """
            返回父结点处业务元素在列表中的索引
            :param j: 任意结点处的业务元素在列表中的索引
            :return: 父结点处业务元素在列表中的索引
            """
            return (j - 1) // 2
    
        def _left(self, j):
            """
            返回左子结点处业务元素在列表中的索引
            :param j: 任意结点处的业务元素在列表中的索引
            :return: 左子结点处业务元素在列表中的索引
            """
            return 2 * j + 1
    
        def _right(self, j):
            """
            返回右子结点处业务元素在列表中的索引
            :param j: 任意结点处的业务元素在列表中的索引
            :return: 右子结点处业务元素在列表中的索引
            """
            return 2 * j + 2
    
        def _has_left(self, j):
            """
            如结点有左子结点则返回True,否则返回False
            :param j: 任意结点处的业务元素在列表中的索引
            :return: 判断结点是否有左子结点的Boolean结果
            """
            return self._left(j) < len(self._data)  # 确保列表索引不越界
    
        def _has_right(self, j):
            """
            如结点有右子结点则返回True,否则返回False
            :param j: 任意结点处的业务元素在列表中的索引
            :return: 判断结点是否有右子结点的Boolean结果
            """
            return self._right(j) < len(self._data)  # 确保列表索引不越界
    
        def _swap(self, i, j):
            """
            交换一对父子结点的业务元素
            :param i: 业务元素在列表中的索引
            :param j: 业务元素在列表中的索引
            :return: None
            """
            self._data[i], self._data[j] = self._data[j], self._data[i]
    
        def _upheap(self, j):
            """
            自堆底向上冒泡算法
            :param j: 结点处业务元素在列表中的索引
            :return: None
            """
            parent = self._parent(j)
            if j > 0 and self._data[j] < self._data[parent]:
                self._swap(j, parent)
                self._upheap(parent)  # 递归调用
    
        def _downheap(self, j):
            """
            自堆顶向下冒泡算法
            :param j: 结点处业务元素在列表中的索引
            :return: None
            """
            if self._has_left(j):
                left = self._left(j)
                small_child = left
                # 如果有左、右两个子结点,令small_child引用键较小子结点的业务元素在列表中的索引
                if self._has_right(j):
                    right = self._right(j)
                    if self._data[right] < self._data[left]:
                        small_child = right
                # 至少根结点有左子结点时,才有可能self虽然是完全二叉树但不是堆
                if self._data[small_child] < self._data[j]:
                    self._swap(j, small_child)
                    self._downheap(small_child)  # 递归调用
    
        def __len__(self):
            """返回优先级队列中的记录条目数"""
            return len(self._data)
    
        def __iter__(self):
            """生成优先级队列中所有记录的一个迭代"""
            for each in self._data:
                yield each
    
        def add(self, key, value):
            """向优先级队列中插入一条key-value记录"""
            self._data.append(self._Item(key, value))  # 新记录条目插入并确保完全二叉树性质
            self._upheap(len(self._data) - 1)  # 确保满足堆序性质
    
        def min(self):
            """返回(但不删除)优先级队列中键最小的记录,如优先级队列此时为空则抛出异常"""
            if self.is_empty():
                raise Empty('优先级队列为空!')
            item = self._data[0]
            return item.key, item.value
    
        def remove_min(self):
            """回并删除优先级队列中键最小的记录,如优先级队列此时为空则抛出异常"""
            if self.is_empty():
                raise Empty('优先级队列为空!')
            self._swap(0, len(self._data) - 1)  # 将根结点处键最小记录交换至完全二叉树最底层最右侧结点处
            item = self._data.pop()
            self._downheap(0)  # 确保完全二叉树满足堆序性质,即确定需保存在根结点处的键最小记录
            return item.key, item.value
    
    
    if __name__ == '__main__':
        heap_queue = HeapPriorityQueue()
        print(heap_queue.is_empty())  # True
    
        heap_queue.add(4, 'C')
        heap_queue.add(6, 'Z')
        heap_queue.add(7, 'Q')
        heap_queue.add(5, 'A')
        print(heap_queue)  # [(4, 'C'), (5, 'A'), (7, 'Q'), (6, 'Z')]
    
        heap_queue.add(2, 'T')
        print(heap_queue)  # [(2, 'T'), (4, 'C'), (7, 'Q'), (6, 'Z'), (5, 'A')]
    
        print(heap_queue.remove_min())  # (2, 'T')
        print(heap_queue.remove_min())  # (4, 'C')
        print(heap_queue)  # [(5, 'A'), (6, 'Z'), (7, 'Q')]
        print(heap_queue.min())  # (5, 'A')
        print(heap_queue.is_empty())  # False
    
    

    实际上,虽然我们在分析自底向上建堆方式时假设给定的价值对个数为 n = 2 h + 1 − 1 n=2^{h+1}-1 n=2h+11个,但实际上对于任意数量的键值对,上述实现的_heapify()方法均支持,具体留待读者思考。

    三、参考资料

    展开全文
  • 因为初始化建堆的过程,是一个杂乱无序的数组构成的完全二叉树,所以需要从第一个非叶节点开始与它的叶子节点进行比较,然后移动。不是说每一层选一个根节点进行比较就可以了,是每一层的所有元素都要跟它的左右节点...

    堆排序分为

    因为初始化建堆的过程,是一个杂乱无序的数组构成的完全二叉树,所以需要从第一个非叶节点开始与它的叶子节点进行比较,然后移动。不是说每一层选一个根节点进行比较就可以了,是每一层的所有元素都要跟它的左右节点进行比较。这也就导致了它的时间复杂度不是logn,对于重建堆的过程,因为是从最上面的根节点开始进行左右节点的比较,选择一个较小的左节点或者有节点进行交换。而因为只破坏了一层的有序性,另外一边的子树的有序性没有遭到破坏,所以,另外一边不需要进行比较,所以,每一层只需要比较一次,一共logn层,需要比较logn次。而一共会有n个这样的元素会被放到根节点进行这样的操作,得到n*lognn。

    插入:堆的插入过程也是在一个有序的堆后面插入一个元素,所以每次只需要跟它的根节点进行比较即可,最多移动的次数是logn次。

    删除:这个暂时还不懂

    1.初始化建立堆(自下而上建立堆)

    2.输出堆顶元素之后,将堆最末的元素跟堆顶元素进行交换

    然后对这个数据结构重新建堆,从上往下进行建堆

    时间复杂度

            堆排序的时间复杂度,主要在初始化堆过程和每次选取最大数后重新建堆的过程;

              初始化建堆过程时间:O(n)

            推算过程:

            首先要理解怎么计算这个堆化过程所消耗的时间,可以直接画图去理解;

            假设高度为k,则从倒数第二层右边的节点开始,这一层的节点都要执行子节点比较然后交换(如果顺序是对的就不用交换);倒数第三层呢,则会选择其子节点进行比较和交换,如果没交换就可以不用再执行下去了。如果交换了,那么又要选择一支子树进行比较和交换;

            那么总的时间计算为:s = 2^( i - 1 )  *  ( k - i );其中 i 表示第几层,2^( i - 1) 表示该层上有多少个元素(跟堆的重建过程不一样的是,这里对每一层的元素都要进行交换的操作。但是对于堆的重建,只需要选择一个分支进行比较),( k - i) 表示子树上要比较的次数,如果在最差的条件下,就是比较次数后还要交换;因为这个是常数,所以提出来后可以忽略;

            S = 2^(k-2) * 1 + 2^(k-3)*2.....+2*(k-2)+2^(0)*(k-1)  ===> 因为叶子层不用交换,所以i从 k-1 开始到 1;

            这个等式求解,我想高中已经会了:等式左右乘上2,然后和原来的等式相减,就变成了:

            S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)

            除最后一项外,就是一个等比数列了,直接用求和公式:S = {  a1[ 1-  (q^n) ] }  / (1-q);

            S = 2^k -k -1;又因为k为完全二叉树的深度,所以 (2^k) <=  n < (2^k  -1 ),总之可以认为:k = logn (实际计算得到应该是 log(n+1) < k <= logn );

            综上所述得到:S = n - longn -1,所以时间复杂度为:O(n)(堆的初始化过程)

    自上向下调整堆结构:
            更改堆元素后重建堆时间:O(nlogn)

            推算过程:

     其中h = log2(n+1)-1,第k层结点个数为2k个(当然最后一层结点个数可能小于2h)。第k层的一个结点插入之后需要进行的比较(移动)次数为k。于是总的比较(移动)次数为∑k*2k(k = 0,1,2,...,h)。可以求得∑k*2k(k = 0,1,2,...,h)=(log2(n+1)-2)*(n+1)+2 = O(n*log2n)

    可以这么理解,对于第k层的元素,最多需要移动的次数是k次,这样就移动了底层。k层的元素一共有2的k次方,那么需要移动的次数就是k*log2 k次数。


    空间复杂度
            因为堆排序是就地排序,空间复杂度为常数:O(1)
    ---------------------
    作者:庾志辉
    来源:CSDN
    原文:https://blog.csdn.net/yuzhihui_no1/article/details/44258297
    版权声明:本文为博主原创文章,转载请附上博文链接!

    展开全文
  • 是一棵二叉树T,该树在它的位置(节点)上存储了集合中的元组并且满足两个附加的属性:关系属性以存储键的形式在T中定义;结构属性以树T自身形状的方式定义。 关系属性:在T中,对于除了根的每个位置p,存储在p中...


    堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
    堆中某个节点的值总是不大于或不小于其父节点的值;
    堆总是一棵完全二叉树。
    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆

    基于数组的完全二叉树表示
    如果p是T的根节点,则f§=0
    如果p是位置q的左孩子,则 f§=2f(q)+1
    如果p是位置q的右孩子,则f§=2
    f(q)+2
    1我们用数组来表示一棵二叉树
    自底向上构建堆
    如初始序列为 3 4 5 7 9 1 2 10 11
    完全二叉树
    在这里插入图片描述在这里插入图片描述

    根据这个完全二叉树构造成小根堆,就要从最后一个具有孩子节点的节点开始不断让其向下调整 ,所以应该从7开始调整,它是最后一个节点的双亲节点所以很容易定位到它 7比2小交换 然后接着调整5 5比1小交换 接着调整4 4 比2小交换 最后调整3 3比1小交换

    基于堆的优先级队列实现

    class Empty:
        pass
    class PriorityQueueBase:
        class _Item:
            def __init__(self,k,v):
                self._key=k#键
                self._value=v#值
            def __It__(self,other):
                return self._key<other._key
        def is_empty(self):
            return len(self)==0
    class HeapPriorityQueue(PriorityQueueBase):
        def __init__(self,content=()):#初始化,用列表作为存储结构
            #self._data=[]
            self._data=[self._Item(k,v) for k,v in content]
            if len(self._data)>1:
               self._heapify()
        def _heapify(self):
            start = self._parent(len(self._data) - 1)
            for i in range(start, -1, -1):
                self._downheap(i)
        def _parent(self,j):#返回下标为j的元素的父节点下标
            return (j-1)//2
        def _left(self,j):#返回下标为j的元素的左孩子下标
            return 2*j+1
        def _right(self,j):#返回下标为j的元素的右孩子下标
            return 2*j+2
        def _has_left(self,j):#判断下标为j的元素是否有左孩子
           return self._left(j)<len(self._data)
        def _has_right(self,j):#判断下标为j的元素是否有右孩子
          return self._right(j)<len(self._data)
        def _swap(self,i,j):#交换self._data数组中下标为i,j的值
            self._data[i],self._data[j]=self._data[j],self._data[i]
        def _upheap(self,j):#自下而上的调整堆
            parent=self._parent(j)
            if j>0 and self._data[j].__It__(self._data[parent]):
                self._swap(j,parent)
                self._upheap(parent)
        def _downheap(self,j):#自上而下的调整堆
            if self._has_left(j):
                left=self._left(j)
                smallchild=left
                if self._has_right(j):
                    right=self._right(j)
                    if self._data[right].__It__(self._data[left]):
                        smallchild=right
                if self._data[smallchild].__It__(self._data[j]):
                    self._swap(j,smallchild)
                    self._downheap(smallchild)
        def __len__(self):
              return len(self._data)
        def add(self,key,value):
            node=self._Item(key,value)
            self._data.append(node)
            self._upheap(len(self._data)-1)
        def min(self):
            if self.is_empty():
                raise Empty('Priority queue is empty')
            item=self._data[0]
            return (item._key,item._value)
        def remove_min(self):
            if self.is_empty():
                raise Empty('Priority queue is empty')
            self._swap(0, len(self._data) - 1)
            item=self._data.pop()
            self._downheap(0)
            return (item._key,item._value)
    HPQ=HeapPriorityQueue()
    HPQ.add(10,2)
    HPQ.add(9,2)
    HPQ.add(5,3)
    HPQ.add(8,7)
    HPQ.add(1,3)
    print(HPQ.min())
    print(HPQ.remove_min())
    print(HPQ.remove_min())
    print(HPQ.remove_min())
    

    基于堆的优先级队列的分析

    操作未排序列表
    LenO(1)
    is_emptyO(1)
    addO(logn)
    minO(1)
    remove_minO(logn)
    展开全文
  • 自底向上实现排序

    千次阅读 2013-05-13 20:01:16
    排序是变治法的一个实例 以实现大根为例 首先,设置一个数组h[N]存储,第一个元素h[0] = INF,不作使用,元素从1到n; 其次,完全二叉树是指:除最后一层,树的每层是满的,最后一层最右边的元素可以...

    堆排序是变治法的一个实例

    以实现大根堆为例


    首先,设置一个数组h[N]存储堆,第一个元素h[0] = INF,不作使用,堆元素从1到n;

    其次,完全二叉树是指:除最后一层,树的每层是满的,最后一层最右边的元素可以缺少;


    堆需要满足两个条件:

    (1)堆逻辑上看是一颗完全二叉树,这具备了一些性质:如父母结点(非叶子结点)下标一定是从1到n/2('/'为整除)

    (2)父母结点的键值(key)一定要大于其孩子(完全二叉树中,父母结点的就是至少存在左孩子的结点)的键值

    我们可以把叶子也看成是一个堆


    堆排序

    如何维护一个堆呢?

    如果从堆顶(第0层)开始,那么调整第一层后,还要继续往下一层调整,下一层的调整却有可能使上一层的不满足第2个条件

    例如一个数组存储为INF 3  5  6 7 9的堆,调整为6 5 3 7 9时,再调整为6 9 3 7 5,这时要需要回到上一层去调整,调整后9 6 3 7 5,又需要继续下一层的调整

    所以:自底向上自右向左地对每个父母结点地调整,则每次更新至多更新到倒数第二层;


    第0步:调整为堆

    参数是堆的规模n,和指定需要调节的父母结点(子二叉堆的堆顶元素)

    对于父母结点i,最多更新2次,因为左孩子一定存在,先与左孩子比较,父母键值小就更新,然后检查是否有右孩子,有若此时的父母键值还是小则更新;

    最后检查是否更新了,如果一次都没有更新则退出调整,更新了,则把完成剩余的最后一次交换(父母键值赋值给左孩子或右孩子,设其为y);

    若y是父母结点则继续调整,否则退出调整


    第1步:建堆

    建堆的过程就是自底向上自右向左地对“最小非堆”调整为堆,即自底向上自右向左地对每个父母结点调整

    注意:在调节一个父母结点x时,其下方和右方的父母结点肯定已经满足了条件2;若x需要调节,则对于 与x交换键值的孩子y——若y是父母结点,则再次进行调整,否则结束调整;

    这里可以用递归实现,也可以迭代实现,每个父母结点至多调整规模到倒数第二层


    第2步:堆排序

    直接把堆顶元素输出或取出,然后把最底层最右边的孩子作为堆顶,堆的规模减一

    对当前规模的堆调整为堆,因为其它父母结点已经满足了条件2,只需调整整个堆的堆顶元素h[1]即可

    #include <iostream>
    using namespace std;
    const int N = 1000;
    const int INF = 999999999;
    
    int h[N];
    
    //维护n个元素的堆或者维护其子堆(i用来指定子二叉堆的堆顶元素)
    //当创建堆时,自底向上自右向左地维护子堆
    //当堆排序时,始终维护整个堆,i=1
    //这里可以写成递归形式 也可以写成迭代形式
    void repairHeap(int n, int i)
    {
    	int tmp, pos;
    	while (i <= n/2) {
    		tmp = h[i];
    		pos = i;
    		//最多更新两次
    		if (h[i*2] > h[i]) {
    			h[i] = h[i*2];
    			pos = i*2;
    		}
    		if (i*2+1 <= n && h[i*2+1] > h[i]) {
    			h[i] = h[i*2+1];
    			pos = i*2+1;
    		}
    		//无更新则退出循环 有更新则完成交换
    		if (pos == i) break;
    		else h[pos] = tmp;
    		i = pos;
    	}
    }
    
    //建堆
    //自底向上自右向左地对父母结点进行更新(维护一个子堆)
    void createHeap(int n)
    {
    	for (int i = n/2; i != 0; i--) {
    		repairHeap(n, i);
    	}
    }
    
    //从大到小输出n个数
    void heapSort(int n)
    {
    	int ntimes = n;
    	while (ntimes--) {
    		printf("%d ", h[1]);
    		h[1] = h[n];
    		h[n--] = 0; //清零
    		repairHeap(n, 1); //始终维护堆顶1
    	}
    	printf("\n");
    }
    int main()
    {
    	int n;
    
    	cin >> n;
    	h[0] = INF;
    	for (int i = 1; i != n+1; i++) {
    		cin >> h[i];
    	}
    	createHeap(n);
    	heapSort(n);
    	return 0;
    }
    



    需要注意的是:堆排序完成后,堆也被修改了,因为排序是就地的。

    对于在堆中插入删除数据,也不难实现了

    插入数据,是指在建堆后插入,插入到最后一个元素后面,然后再调整堆

    删除数据,是指删除指定的合法下标的元素,然后再调整堆

    #include <iostream>
    using namespace std;
    const int N = 1000;
    const int INF = 999999999;
    
    int h[N];
    
    //维护n个元素的堆或者维护其子堆(i用来指定子二叉堆的堆顶元素)
    //当创建堆时,自底向上自右向左地维护子堆
    //当堆排序时,始终维护整个堆,i=1
    //这里可以写成递归形式 也可以写成迭代形式
    void repairHeap(int n, int i)
    {
    	int tmp, pos;
    	while (i <= n/2) {
    		tmp = h[i];
    		pos = i;
    		//最多更新两次
    		if (h[i*2] > h[i]) {
    			h[i] = h[i*2];
    			pos = i*2;
    		}
    		if (i*2+1 <= n && h[i*2+1] > h[i]) {
    			h[i] = h[i*2+1];
    			pos = i*2+1;
    		}
    		//无更新则退出循环 有更新则完成交换
    		if (pos == i) break;
    		else h[pos] = tmp;
    		i = pos;
    	}
    }
    
    //建堆
    //自底向上自右向左地对父母结点进行更新(维护一个子堆)
    void createHeap(int n)
    {
    	for (int i = n/2; i != 0; i--) {
    		repairHeap(n, i);
    	}
    }
    
    //从大到小输出n个数x
    void heapSort(int n)
    {
    	int ntimes = n;
    	while (ntimes--) {
    		printf("%d ", h[1]);
    		h[1] = h[n];
    		h[n--] = 0; //清零
    		repairHeap(n, 1); //始终维护堆顶1
    	}
    	printf("\n");
    }
    
    //加入一个元素
    //必须是加入到最后位置,然后找到其父母结点,自底向上自右向左地调整所有父母结点
    //必须修改堆的规模,这里要引用规模n
    void insertElement(int& n, int key)
    {
    	h[++n] = key;
    	//调整为堆
    	for (int i = n/2; i != 0; i--) {
    		repairHeap(n, i);
    	}
    }
    
    
    //删除一个元素
    //类似删除第一个元素,直接输出或取出,然后用最后一个元素取代它,更新这个子堆
    void deleteElement(int& n, int x)
    {
    	if (x < 1 || x > n)
    		return;
    	h[x] = h[n--];
    	//调整为堆
    	repairHeap(n, x);
    }
    
    
    int main()
    {
    	int n;
    
    	//新数据
    	cin >> n;
    	h[0] = INF;
    	for (int i = 1; i != n+1; i++) {
    		cin >> h[i];
    	}
    	//建堆
    	createHeap(n);
    	for (int i = 1; i != n+1; i++) {
    		cout << h[i] << " ";
    	}
    	cout << endl;
    	
    	heapSort(n); //堆排序后,堆已经被销毁了
    	
    	//新数据
    	cin >> n;
    	h[0] = INF;
    	for (int i = 1; i != n+1; i++) {
    		cin >> h[i];
    	}
    	//建堆
    	createHeap(n);
    	for (int i = 1; i != n+1; i++) {
    		cout << h[i] << " ";
    	}
    	cout << endl;
    
    	//插入一个数据
    	cout << "Plese insert a number:" << endl;
    	int key;
    	cin >> key;
    	insertElement(n, key);
    	heapSort(n); //堆排序后,堆已经被销毁了
    
    
    	//新数据
    	cin >> n;
    	h[0] = INF;
    	for (int i = 1; i != n+1; i++) {
    		cin >> h[i];
    	}
    	
    	//建堆后
    	createHeap(n);
    	for (int i = 1; i != n+1; i++) {
    		cout << h[i] << " ";
    	}
    	cout << endl;
    
    	//建堆后删除一个数据(指定下标)
    	cout << "Plese enter a index to delete the number:" << endl;
    	int pos; //pos belongs to [1, n]
    	cin >> pos;
    	deleteElement(n, pos);
    	heapSort(n); //堆排序后,堆已经被销毁了x
    	
    	return 0;
    }
    
    /*
      数据测试参考
    6
    8 2 4 6 9 1
    
    6
    8 2 4 6 9 1
    7
    
    6
    8 2 4 6 9 1
    3
     */
    



    展开全文
  • 自下而上建立时间复杂度推导

    千次阅读 2018-08-30 16:59:02
    建立的顺序是bottom-top的。  正确的证明方法应当如下: 具有n个元素的平衡二叉树,树高为㏒n,我们设这个变量为h。 最下层非叶节点的元素,只需做一次线性运算便可以确定大根,而这一层具有2^(h-1)个元素,...
  • 阿里妹导读:知识图谱的构建技术主要有顶向下和自底向上两种。其中顶向下构建是指借助百科类网站等结构化数据源,从高质量数据中提取本体和模式信息,加入到知识库里。而自底向上构建,则是借助一定的技术手段,...
  • 【转】自底向上顶向下的区别

    千次阅读 2019-09-27 01:35:05
    自底向上就是先零件图,然后去组装装配图! 三维网技术论坛; b2 c2 d( t9 G" k 顶向下就是先装配图,再在装配图中建零件图! 或者先建立一个总装配体的零件图,然后切割成各个零件图!   两种分析方法的...
  • 最近笔者花了几天时间研究了,下面做一些分享。 首先什么是在逻辑上是特殊的完全二叉树,在存储结构上是顺序表。一般用数组实现。...顶向下算法: 现在我们给出一个数组,逻辑上看...
  • (2)自底向上 4. 的构建和删除节点 4.1 插入节点进 4.2 构建 4.3 删除的节点 5. 排序 6. 前k个问题 本文的代码链接 1. 什么是就是一棵完全二叉树,分为大顶堆和小顶堆 大顶堆:每一个...
  • 是一种完全二叉树,现实中通常使用顺序结构的数组来存储,此处的是一种数据结构(完全二叉树),而不是虚拟进程空间中的那个(是操作系统用来管理内存的一个区域分段 )
  • 堆排序初始建堆的时间复杂度,数据结构算法上写的时间复杂度是O(nlogn),而在网络上搜索,大部分人说是O(n),其实这是一个顶向下建堆和自底向上建堆的问题 顶向下建堆 顶向下建堆的情况可以参考堆排序初始建堆...
  • //关于最小,我们关心的是更小的那个节点 int h[101]; //用于存储数组 int n; //用于存储的大小 void swap(int x, int y) { int temp; temp = h[x]; h[x] = h[y]; h[y] = temp; } void sift_down(int i)...
  • 文章目录基本性质存储方式具体实现向上调整swim向下调整sink实现delMax (删除队顶元素)实现insert完整代码建堆自顶向下建堆自底向上建堆堆排序例题寻找第K大元素 基本性质 优先级队列,也叫二叉堆、堆(不要和内存...
  • 一、建堆 1.堆的概念及性质 如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且...
  • 建立大根时,设有n个记录的初始序列所对应的完全二叉树的深度为h,时,每个非终端结点都要自上而下进行"筛选"。由于第i层上的结点数小于等于i-1,且第i层结点最大下移的深度为h-i,每下移一层要做两次比较,...
  • 堆,建堆,堆排序,堆删除和堆插入

    万次阅读 多人点赞 2018-05-24 23:42:45
    注意:看这篇文章之前,你一定要知道完全二叉树的结构首先要明白一点,是一种数据结构,和队列,链表,树等等一个级别。的定义是一棵节点含有内部比较器的完全二叉树。(说白了,就是完全二叉树,只不过它的...
  • 可以通过siftdown或者siftup建立二叉堆。 siftdown: 如果节点小于其最大的子节点,将二者进行交换,直到节点大于或等于所有子节点。...siftdown的效率更高一些,因为建堆时计算每个节点到底部或者顶部的距离
  • 开源ESB厂商MuleSoft在宣布其管理控制台发布时,声称支持使用底而上的方法来实现SOA管理理念,在这之后,SOA社区中一个一直以来争论不休的话题:使用顶向下还是...\n当增SOA时,一个自底向上的治理方法会关...
  • 文章目录堆排序要点总结建堆详细时间复杂度证明实现代码(python)小根堆测试代码(堆排序正确性测试) 堆排序要点总结 堆的两个要素:是完全二叉树并且父节点的值一定大于(大根堆)或小于(小根堆)它的左右孩子...
  • 算法导论 — 6.3 建堆

    2018-12-03 22:41:16
    建堆的过程实际上是自底向上地对所有非叶结点调用MAX-HEAPIFY的过程。由于叶结点没有孩子,所以每一个叶结点都可以看是只包含一个元素的最大堆。而自底向上地调用MAX-HEAPIFY,是要保证在处理任意一个结点的时候,它...
  • 向上向下调整算法

    千次阅读 2019-06-06 01:24:22
    建堆: 插入关键字3: 从3开始向上调整,让它满足最小堆的特点,过程如下: 3和19交换位置 3和8交换位置: 3和5交换位置 至此交换完毕,满足最小堆的特点,调整后得到的最小堆为3,5,12,8,28,20,15,22,...
  • 但其实它是顺序存储的结构,这里我们实现的是大根堆的建堆算法。 堆排序:建大根堆--&gt;输出堆顶元素(和堆元素交换)--&gt;整理将其重新整理成为堆 (1)大根堆(堆顶元素大于或等于其对应的子节点) L...
  • 建堆、二叉树

    2021-09-07 19:39:42
    方法1:建堆1次(时间复杂度为O(N))找到最小,再在剩下的数里再建1次,得到次小的,继续下去,再建堆选,整个排出来,时间复杂度为O(N*N)。 方法2:建堆1次找到最小,{15,18,29,25,28,34,65,49,27,37},最小的换...
  • 由于建堆过程自底向上,以交换作为主要操作,因此第i层任意节点在最不利情况下,需要经过(n-i)次交换操作才能完成以该节点为堆根节点的建堆过程。因此,时间复杂度计算如下: T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) ...
  • 通俗易懂的讲解排序(含Gif图)

    千次阅读 2020-04-07 16:07:17
    的定义 排序是一种树形结构选择排序方法,其特点是:在排序过程中,将序列视为一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的关系,在当前无序区间中选择关键字最大(或最小)的元素。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,442
精华内容 2,176
关键字:

自底向上的建堆