Notice
Recent Posts
Recent Comments
Link
Kim Jinung
Python - heapq 본문
heapq — Heap queue algorithm — Python 3.11.1 documentation
heapq — Heap queue algorithm Source code: Lib/heapq.py This module provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. Heaps are binary trees for which every parent node has a value less than or equal to an
docs.python.org
heapq 모듈은 heap queue 알고리즘의 구현을 제공한다. (우선순위 큐 알고리즘으로도 알려져있다.)
*주의할 점은 사용하기 전에 힙으로 만들고자 하는 리스트를 heapify 메서드에 넘겨서 힙으로 변경 시켜주어야 한다.
*리스트를 힙으로 변경한 이후에는 heapq 객체의 메서드가 아닌, 리스트의 append 메서드 등을 사용하면 더 이상 힙 조건을 만족하지 않게 된다.
- heap은 트리 기반의 자료구조다.
- BST(Binary Search Tree)는 항상 모든 노드가 정렬된 상태를 유지한다. 즉 탐색과 삽입이 모두 O(N log N)이다.
- 반면에 heap은 정렬을 보장하지 않는다. 최소, 최대 값만을 보장한다. 시간 복잡도는 O(log N)이다.
- 즉 트리에서 모든 노드가 정렬된 상태를 유지해야한다면 BST, 최소 최댓값을 보장해야한다면 된다면 heap을 사용할 수 있다.
heapq 연습 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
'Language > Python' 카테고리의 다른 글
| Python - reduce (0) | 2023.02.11 |
|---|---|
| Python - functools.cmp_to_key (compare sort, 비교 정렬) (0) | 2023.01.19 |
| Python - Counter (0) | 2022.12.06 |
| Python - for/else (0) | 2022.12.02 |
| Python - Regular Expression (0) | 2022.11.30 |