[PY3]——heap模块和堆排序

heapify( )

heapify()函数用于将一个序列转化为初始化堆

nums=[16,7,3,20,17,8,-1]

print('nums:',nums)

show_tree(nums)

nums: [16, 7, 3, 20, 17, 8, -1]

                 16

        7                 3

    20       17       8        -1

------------------------------------

heapq.heapify(nums)

print('nums:',nums)

show_tree(nums)

nums: [-1, 7, 3, 20, 17, 8, 16]

                 -1

        7                 3

    20       17       8        16

------------------------------------

heappush( )

heappush()是实现将元素插入到堆的操作
heappush()操作前一定要先将序列初始化成堆！heappush是对于"堆"的操作！不然是没有意义

nums=[16,7,3,20,17,8,-1]

print(nums)

show_tree(nums)

       [16, 7, 3, 20, 17, 8, -1]

                   16

          7                 3

      20       17       8        -1

  ------------------------------------

heapq.heapify(nums)

print('初始化成堆:',nums)

show_tree(nums)

    初始化成堆: [-1, 7, 3, 20, 17, 8, 16]

                     -1

            7                 3

        20       17       8        16

    ------------------------------------

for i in random.sample(range(1,8),2):

    print("本次push:",i)

    heapq.heappush(nums,i)

    print(nums)

    show_tree(nums)

    本次push: 5

    [-1, 5, 3, 7, 17, 8, 16, 20]

                     -1

            5                 3

        7        17       8        16

     20

    ------------------------------------

    本次push: 7

    [-1, 5, 3, 7, 17, 8, 16, 20, 7]

                     -1

            5                 3

        7        17       8        16

     20  7

    ------------------------------------

heappop( )

heappop()是实现将元素删除出堆的操作
同样的操作前一定要先将序列初始化成堆，否则也没什么意义

nums=[16,7,3,20,17,8,-1]

print(nums)

show_tree(nums)

          [16, 7, 3, 20, 17, 8, -1]

                       16

              7                 3

          20       17       8        -1

      ------------------------------------

heapq.heapify(nums)

print('初始化成堆:',nums)

show_tree(nums)

        初始化成堆: [-1, 7, 3, 20, 17, 8, 16]

                         -1

                7                 3

            20       17       8        16

        ------------------------------------

for i in range(0,2):

    print("本次pop：",heapq.heappop(nums))

    print(nums)

    show_tree(nums)

        本次pop： -1

        [3, 7, 8, 20, 17, 16]

                         3

                7                 8

            20       17       16

        ------------------------------------

        本次pop： 3

        [7, 16, 8, 20, 17]

                         7

                16                8

            20       17

        ------------------------------------

nlargest( )/nsmallest( )

sorted(iterable, key=key, reverse=True)[:n]

nlargest(n,iterable) 求序列iterable中的TopN | nsmallest(n,iterable) 求序列iterable中的BtmN

import heapq

nums=[16,7,3,20,17,8,-1]

print(heapq.nlargest(3,nums))

print(heapq.nsmallest(3,nums))

[20, 17, 16]

[-1, 3, 7]

nlargest(n, iterable, key=lambda) | nsmallest(n, iterable, key=lambda) key接受关键字参数，用于更复杂的数据结构中

def print_price(dirt):

    for i in dirt:

        for x,y in i.items():

            if x=='price':

                print(x,y)

portfolio = [

    {'name': 'IBM', 'shares': 100, 'price': 91.1},

    {'name': 'AAPL', 'shares': 50, 'price': 543.22},

    {'name': 'FB', 'shares': 200, 'price': 21.09},

    {'name': 'HPQ', 'shares': 35, 'price': 31.75},

    {'name': 'YHOO', 'shares': 45, 'price': 16.35},

    {'name': 'ACME', 'shares': 75, 'price': 115.65}

]

cheap=heapq.nsmallest(3,portfolio,key=lambda x:x['price'])

expensive=heapq.nlargest(3,portfolio,key=lambda y:y['price'])

print_price(cheap)

print_price(expensive)

price 16.35

price 21.09

price 31.75

price 543.22

price 115.65

price 91.1