Python heapq 사용 상세 설명 및 인 스 턴 스 코드

파 이 썬 heapq 상세 설명
Python 에는 내 장 된 모듈 이 있 습 니 다.hepq 표준 은 최소 로 포 장 된 알고리즘 이 구현 되 었 습 니 다.다음은 두 가지 괜 찮 은 애플 리 케 이 션 을 보 겠 습 니 다.
작은 꼭대기 더미(TopK 대)
그러나 수 요 는 이 렇 습 니 다.긴 서열 을 정 하고 TopK 큰 데 이 터 를 구 합 니 다.

import heapq
import random

class TopkHeap(object):
  def __init__(self, k):
    self.k = k
    self.data = []

  def Push(self, elem):
    if len(self.data) < self.k:
      heapq.heappush(self.data, elem)
    else:
      topk_small = self.data[0]
      if elem > topk_small:
        heapq.heapreplace(self.data, elem)

  def TopK(self):
    return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])]

if __name__ == "__main__":
  print "Hello"
  list_rand = random.sample(xrange(1000000), 100)
  th = TopkHeap(3)
  for i in list_rand:
    th.Push(i)
  print th.TopK()
  print sorted(list_rand, reverse=True)[0:3]

큰 꼭대기 더미(BtmK 작은 것 을 구하 세 요)
이번 수 요 는 더욱 어려워 졌 다.N 의 긴 서열 을 제시 하고 BtmK 의 작은 요 소 를 구 했다.즉,큰 무 더 기 를 사용 하 는 것 이다.
알고리즘 실현 의 핵심 사고방식 은 push(e)를 push(-e),pop(e)를-pop(e)로 바 꾸 는 것 이다.

class BtmkHeap(object):
  def __init__(self, k):
    self.k = k
    self.data = []

  def Push(self, elem):
    # Reverse elem to convert to max-heap
    elem = -elem
    # Using heap algorighem
    if len(self.data) < self.k:
      heapq.heappush(self.data, elem)
    else:
      topk_small = self.data[0]
      if elem > topk_small:
        heapq.heapreplace(self.data, elem)

  def BtmK(self):
    return sorted([-x for x in self.data])

 읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!

좋은 웹페이지 즐겨찾기