T I L / 5월 25일

Heap

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

이런 구조로 데이터를 정렬해주는 자료구조.
리스트 형식이고 push 순서대로 상단으로, 왼쪽부터 채워진다. 숫자가 있는 자리를 노드, 숫자와 숫자를 이어주는 선을 간선(링크) 라고 한다. 노드 3개가 기본 구조인데 윗층에 노드 하나, 그 하단 양쪽에 노드가 있는 형식이다. 최소힙이 기본 구조인데 최소힙이란 데이터를 삽입했을 때 상단의 노드보다 작으면 둘이 자리를 바꾸는 동작을 반복해 가장 작은 값이 최 상단 자리를 차지하는 방식이다.

import heapq
a = []
heapq.heappush(a,5)
heapq.heappop(a)

push하면 상단 왼쪽부터 자리를 잡고, pop하면 최상단 값이 도출된다.
리스트처럼 인덱스로(ex. a[0]) 데이터를 소환할 수도 있고 인덱스도 0 부터 시작한다.

읽은 글

• 공개적으로 학습하라
• <하루 3분 네트워크 교실>