heapq 모듈은 힙 알고리즘을 제공합니다. heapq는 자식 노드와 부모 노드가 정렬되어 있는 트리 데이터 구조입니다. 이 모듈은 heap[k]
힙 q 유형 인쇄
import math import random from cStringIO import StringIO def show_tree(tree, total_width=36, fill=' '): output = StringIO() last_row = -1 for i, n in enumerate(tree): if i: row = int(math.floor(math.log(i+1, 2))) else: row = 0 if row != last_row: output.write('\n') columns = 2**row col_width = int(math.floor((total_width * 1.0) / columns)) output.write(str(n).center(col_width, fill)) last_row = row print output.getvalue() print '-' * total_width print return data = random.sample(range(1,8), 7) print 'data: ', data show_tree(data)
결과 인쇄
data: [3, 2, 6, 5, 4, 7, 1] 3 2 6 5 4 7 1 ------------------------- heapq.heappush(heap, item)
요소를 힙에 푸시하고 위 코드를 수정
heap = [] data = random.sample(range(1,8), 7) print 'data: ', data for i in data: print 'add %3d:' % i heapq.heappush(heap, i) show_tree(heap)
결과 인쇄
data: [6, 1, 5, 4, 3, 7, 2] add 6: 6 ------------------------------------ add 1: 1 6 ------------------------------------ add 5: 1 6 5 ------------------------------------ add 4: 1 4 5 6 ------------------------------------ add 3: 1 3 5 6 4 ------------------------------------ add 7: 1 3 5 6 4 7 ------------------------------------ add 2: 1 3 2 6 4 7 5 ------------------------------------
결과에 따르면, 자식 노드의 요소가 부모 노드의 요소보다 크다는 것을 알 수 있습니다. 형제 노드는 정렬되지 않습니다.
heapq.heapify(list)
목록 유형을 힙으로 변환하고 목록을 선형 시간으로 재정렬합니다.
print 'data: ', data heapq.heapify(data) print 'data: ', data show_tree(data)
결과 인쇄
data: [2, 7, 4, 3, 6, 5, 1] data: [1, 3, 2, 7, 6, 5, 4] 1 3 2 7 6 5 4 ------------------------------------ heapq.heappop(heap)
힙에서 가장 작은 요소를 제거하고 반환합니다. heapify() 및 heappop()을 사용하여 정렬합니다.
data = random.sample(range(1, 8), 7) print 'data: ', data heapq.heapify(data) show_tree(data) heap = [] while data: i = heapq.heappop(data) print 'pop %3d:' % i show_tree(data) heap.append(i) print 'heap: ', heap
결과 인쇄
data: [4, 1, 3, 7, 5, 6, 2] 1 4 2 7 5 6 3 ------------------------------------ pop 1: 2 4 3 7 5 6 ------------------------------------ pop 2: 3 4 6 7 5 ------------------------------------ pop 3: 4 5 6 7 ------------------------------------ pop 4: 5 7 6 ------------------------------------ pop 5: 6 7 ------------------------------------ pop 6: 7 ------------------------------------ pop 7: ------------------------------------ heap: [1, 2, 3, 4, 5, 6, 7]
정렬된 힙을 볼 수 있습니다.
heapq.heapreplace(iterable, n)
기존 요소를 제거하고 새 값으로 바꿉니다.
data = random.sample(range(1, 8), 7) print 'data: ', data heapq.heapify(data) show_tree(data) for n in [8, 9, 10]: smallest = heapq.heapreplace(data, n) print 'replace %2d with %2d:' % (smallest, n) show_tree(data)
결과 인쇄
data: [7, 5, 4, 2, 6, 3, 1] 1 2 3 5 6 7 4 ------------------------------------ replace 1 with 8: 2 5 3 8 6 7 4 ------------------------------------ replace 2 with 9: 3 5 4 8 6 7 9 ------------------------------------ replace 3 with 10: 4 5 7 8 6 10 9 ------------------------------------
heapq.nlargest(n, iterable ) 및 heapq.nsmallest(n, iterable)
n개의 최대값과 최소값을 목록에 반환
data = range(1,6) l = heapq.nlargest(3, data) print l # [5, 4, 3] s = heapq.nsmallest(3, data) print s # [1, 2, 3]
PS: 계산 문제
요소 수 K=5로 최소 힙 코드 예제 구성:
#!/usr/bin/env python # -*- encoding: utf-8 -*- # Author: kentzhan # import heapq import random heap = [] heapq.heapify(heap) for i in range(15): item = random.randint(10, 100) print "comeing ", item, if len(heap) >= 5: top_item = heap[0] # smallest in heap if top_item < item: # min heap top_item = heapq.heappop(heap) print "pop", top_item, heapq.heappush(heap, item) print "push", item, else: heapq.heappush(heap, item) print "push", item, pass print heap pass print heap print "sort" heap.sort() print heap
결과:
Python에서 heapq 모듈 사용과 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!