• 技术文章 >Python技术 >Python基础教程

    python数据结构堆的介绍

    小妮浅浅小妮浅浅2021-08-27 09:15:30原创3016

    说明

    1、堆是用数据结构来实现的一种算法:树,数组均可。堆本身是一棵完全二叉树。

    2、特点,堆:所有父节点的值大于子节点的值。最小堆,所有父节点的值小于子节点的值。

    实例

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    42

    43

    44

    45

    46

    47

    48

    49

    class Heap(object):

        def __init__(self, list=[]):

            self.root = None

            self.list = list

            self.tree = None

            self.len = len(list)

      

        # 建堆

        def bulid_heap(self):

            if self.list != []:

                final_parent_node = int((self.len - 1) / 2)

                while final_parent_node >= 0:

                    self.heapfy(final_parent_node, self.len)

                    final_parent_node -= 1

      

        # 对当前节点以及向下所有子节点的一次节点交换

        def heapfy(self, node, len):

            node_left = 2 * node + 1

            node_right = 2 * node + 2

            max = node

            if node_left < len and self.list[node_left] > self.list[max]:

                max = node_left

            if node_right < len and self.list[node_right] > self.list[max]:

                max = node_right

            if max != node:

                self.swap(max, node)

                self.heapfy(max, len)

      

        # 交换元素方法

        def swap(self, i, j):

            self.list[j], self.list[i] = self.list[i], self.list[j]

      

        # 堆排序

        def heap_sort(self):

            len = self.len - 1

            while len >= 0:

                self.swap(0, len)

                self.heapfy(0, len)

                len -= 1

      

      

    if __name__ == "__main__":

        list = [5, 7, 3, 1, 10, 0]

        heap = Heap(list)

        print("初始列表:{}".format(heap.list))

        heap.bulid_heap()

        print("堆化:{}".format(heap.list))

        heap.heap_sort()

        print("排序:{}".format(heap.list))

    以上就是python数据结构堆的介绍,希望对大家有所帮助。更多Python学习指路:python基础教程

    本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。

    专题推荐:python数据结构
    上一篇:python中os.path.join()函数是什么 下一篇:python参数调用的注意点

    相关文章推荐

    • Python数据分析 | pandas汇总和计算描述统计• python数据怎么添加列?• python数据处理是什么意思• python数据分析是什么• python数据形式有哪些• python数据变换如何实现• python数据预处理的三种情况• python数据拼接如何实现• python数据离散化是什么• Python数据可视化库有哪些

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网