Heapqを使ってみた

はじめに

pythonのheapqというライブラリを使って，ソートを行う方法を学んだのでメモしました．

heapqとは

• heapq: ヒープキューアルゴリズムを利用できるライブラリ．ヒープキューは優先度キューの一種．全ての親の値が，その全ての子の値以下であるようなツリー構造を持ち，その構造を利用して効率的に要素を取り出す．
• キュー：複数要素の並び
• 優先度キュー：ある優先度に従って要素を取り出す仕組みを持つキュー．

ヒープキューは，主にソートに用いられる（ヒープソート）．

実行時間については，
全ての値の大小を比較するバブルソートの場合，$O(N^2)$．
対して，ヒープソートの場合，$O(NlogN)$．

heapqを使って，leetcodeの問題を解いてみた

問題リンク：
https://leetcode.com/problems/kth-largest-element-in-a-stream/discuss/482591/Simple-Python-Solution-or-Maintain-Min-Heap-whose-size-is-always-kept-at-k

import heapq

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.heap = []
        self.k = k

        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:

        heapq.heappush(self.heap, val)

        if len(self.heap) > self.k:
            heapq.heappop(self.heap)

        return self.heap[0]