반응형
자료구조 선형자료구조
-
[ Data Structure ] Heap 힙 & 우선순위 큐공부 !/Computer Science 2022. 4. 14. 23:44
Heap 힙은 어떤 자료구조인가 ! 비선형 자료구조의 일종으로 최소값과 최대값을 빠르게 찾기 위한 이진트리 구조이다 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다 힙은 heapq 내장 모듈로 구현할 수 있고 우선순위 큐는 힙으로 구현이 가능하다 ! 최소 힙은 각 노드의 키 값이 그 자식노드의 키 값보다 크지 않은 힙을 의미하고 최대 힙은 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙을 의미한다 힙은 완전이진트리의 성질을 갖고 1차원 배열로 표현이 가능하다 아래를 참고하면 root index 에 따라 chlid index 를 계산할 수 있다 root index = 0 left index = index * 2 + 1 right index = index * 2 + 2 ..