[파이썬 알고리즘 인터뷰] 힙

• 힙: 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리
  • 파이썬에는 최소 힙만 구현(heapq 모듈)
  • 우선순위 큐에서 가장 작은 값을 가져올때 매번 최소 힙의 루트를 가져오면 된다
  • 부모 자식 간의 관계만 정의하므로 정렬된 구조가 아님
  • 자식이 둘인 힙은 이진 힙이라 하며, 이진 트리와 마찬가지 이유로 대부분 이진 힙이 널리 사용됨
  • 배열에 순서대로 표현하기 좋으며, 편한 계산을 위해 인덱스는 1부터 사용
  • 다익스트라 알고리즘, 힙 정렬, 최소 신장 트리, 프림 알고리즘, 중앙값의 근삿값
• 힙 연산(최소 힙): 삽입(업힙) -> O(logn), 추출(다운힙) -> O(logn), 이진 힙은 조회할 때 O(1)
  • 삽입: 요소를 최하위 레벨의 가장 왼쪽으로 삽입 -> 부모와 비교 후 값이 더 작으면 스왑 -> 계속 비교 및 스왑
  • 추출: 루트 추출 -> 마지막 요소를 루트에 위치 -> 자식과 비교 후 값이 더 크면 스왑 -> 계속 비교 및 스왑
  • 클래스에서 __method__() 형태는 매직 메소드로 여러 내부 기능이 동작되는 데 사용된다
    • 예: len(a)를 하면 내부적으로 a.__len__() 호출하여 결과 리턴 (__len__()는 내장된 len()과 다르게 설정)
  • ※ BST는 탐색과 삽입 모두 O(logn)

215. Kth Largest Element in an Array

- heapq 모듈 이용해 배열이 최대 힙 특성을 갖도록 음수로 저장한 다음, 가장 낮은 수부터 추출해 부호 변환

- heapq 모듈의 heapify 이용해 배열이 (최소) 힙 특성을 갖도록 하고, n번째로 큰 수 = len(nums) - k + 1번째로 작은 수

- heapq 모듈의 nlargest 모듈로 바로 n번째로 큰 요소 추출

- 리스트 정렬하여 인덱스로 추출

- 내 실수: 리스트를 힙 특성을 갖도록 하는 과정 생략하고 추출함