Code examples for implementing binary heap and heap sorting in Python-Python Tutorial-php.cn

Code examples for implementing binary heap and heap sorting in Python

黄舟

Release： 2017-10-02 19:40:45

Original

1522 people have browsed it

The following editor will bring you an example of implementing binary heap and heap sorting in python. The editor thinks it’s pretty good, so I’ll share it with you now and give it as a reference. Let’s follow the editor to take a look.

Heap is a special tree structure, and the data storage in the heap satisfies a certain heap order. Heap sort is a selection sort, and its algorithm complexity and time complexity have great advantages over other sorting algorithms.

Heaps are divided into big-headed heaps and small-headed heaps. As the name suggests, the first element of the big-headed heap is the largest. The data value of each parent node with child nodes is higher than that of its child nodes. The point value should be large. Xiaotou Dui is the opposite.

I will briefly explain the algorithm process of building a tree heap:

Find the array data at position N/2 and start from this position , find the index of the left child node of the node, first compare the child nodes under this node, find the largest one, assign the index of the largest child node to the left child node, and then assign the largest child node The point is compared with the parent node. If it is larger than the parent node, data is exchanged with the parent node. Of course, I just briefly talked about the implementation. During this process, we also need to consider the situation where the node does not exist.

Look at the code:

# 构建二叉堆 
def binaryHeap(arr, lenth, m): 
 temp = arr[m] # 当前结点的值 
 while(2*m+1 < lenth): 
 lchild = 2*m+1 
 if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]: 
 lchild = lchild + 1 
 if temp < arr[lchild]: 
 arr[m] = arr[lchild] 
 else: 
 break 
 m = lchild 
 arr[m] = temp 
 
 
def heapsort(arr, length): 
 i = int(len(arr)/2) 
 while(i >= 0): 
 binaryHeap(arr, len(arr), i) 
 i = i - 1 
 
 print("二叉堆的物理顺序为:") 
 print(arr) # 输出二叉堆的物理顺序 
 
 
if __name__ == '__main__': 
 arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98] 
 
 heapsort(arr, len(arr))

Copy after login

The heap sorting process is to sequentially sort the last node with the first Nodes are compared and exchanged:

# 构建二叉堆
def binaryHeap(arr, lenth, m):
  temp = arr[m] # 当前结点的值
  while(2*m+1 < lenth):
    lchild = 2*m+1
    if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
      lchild = lchild + 1
    if temp < arr[lchild]:
      arr[m] = arr[lchild]
    else:
      break
    m = lchild
  arr[m] = temp


def heapsort(arr, length):
  i = int(len(arr)/2)
  while(i >= 0):
    binaryHeap(arr, len(arr), i)
    i = i - 1

  print("二叉堆的物理顺序为:")
  print(arr) # 输出二叉堆的物理顺序

  i = length-1
  while(i > 0):
    arr[i], arr[0] = arr[0], arr[i] # 变量交换
    binaryHeap(arr, i, 0)
    i = i - 1560


def pop(arr):
  first = arr.pop(0)
  return first


if __name__ == '__main__':
  arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]

  heapsort(arr, len(arr))

  print("堆排序后的物理顺序")
  print(arr) # 输出经过堆排序之后的物理顺序

  data = pop(arr)
  print(data)

  print(arr)

Copy after login

Python encapsulates a heap module. We can use this module to implement a priority queue very efficiently

import heapq


class Item:
  def __init__(self, name):
    self.name = name

  def __repr__(self):
    return 'Item({!r})'.format(self.name)


class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index = 0

  def push(self, item, priority):
    heapq.heappush(self._queue, (-priority, self._index, item)) # 存入一个三元组
    self._index += 1

  def pop(self):
    return heapq.heappop(self._queue)[-1] # 逆序输出


if __name__ == '__main__':
  p = PriorityQueue()
  p.push(Item('foo'), 1)
  p.push(Item('bar'), 5)
  p.push(Item('spam'), 4)
  p.push(Item('grok'), 1)

  print(p.pop())
  print(p.pop())

Copy after login

For details, please see the heapq official website

The above is the detailed content of Code examples for implementing binary heap and heap sorting in Python. For more information, please follow other related articles on the PHP Chinese website!