Heap
heap
우선순위 큐를 위해 만들어진 자료구조
선입선출하는 일반 큐와 다르게, 우선순위가 높은 데이터가 먼저 나가는 시스템
완전 이진 트리의 일종
여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조로 반정렬 상태이다.
중복된 값을 허용한다. - 이진트리는 중복값 허용 안됨
최대 힙
부모 노드의 키 값이 자신 노드의 키 값보다 크거나 같은 완전 이진 트리
최소 힙
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
예시
시뮬레이션 시스템
네트워크 트래픽 제어
운영체제에서의 작업 스케줄링
수치 해석적인 계산
장점
최대값과 최소값을 찾아낼 때에도 시간복잡도 O(1) 로 가능하다.
삽입과 삭제 연산 시에도 트리의 깊이만큼만 탐색하면 되기 때문에 시간 복잡도가 O(logN) 으로 매우 빠르다.
구현
우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 그중에서도 힙으로 표현하는 것이 가장 효율적이다.
힙을 저장하는 표준적인 자료구조는 배열
구현 쉽게 하기 위해서 첫 인덱스인 0은 사용하지 않는다.
각 노드와 대응되는 배열의 인덱스틑 불변한다.
"부모 노드는 항상 자식 노드보다 우선순위가 높다" 는 조건을 기억하며 완전이진트리 형태로 채워나간다.
최소힙, 최대힙
다시 한 번 기억하기
"부모 노드는 항상 자식 노드보다 우선순위가 높다" 는 조건을 기억하며 완전이진트리 형태로 채워나간다.
각 노드와 대응되는 배열의 인덱스는 불변한다.
구현 쉽게 하기 위해서 첫 인덱스인 0은 사용하지 않는다.
힙을 저장하는 표준적인 자료구조는 배열
성질
왼쪽 자식 인덱스 = 부모 인덱스 * 2
오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 1
부모 인덱스 = 자식 인덱스 / 2
참고
Last updated