Heap
Priority Queue(우선순위 큐)
들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
queue에 우선순위 개념을 도입한 자료구조
우선순위 큐는 Array, LinkedList, Heap으로 구현 가능 → Heap으로 구현하는게 가장 효율적
Array
우선순위가 높은 순서대로 배열의 가장 앞부분부터 삽입 →
O(1)
우선순위가 중간인 데이터를 삽입하는 과정에서 위치를 탐색하고 한칸씩 뒤로 밀어야함 →
O(N)
LinkedList
우선순위가 높은 데이터를 head에 위치하도록 삽입 →
O(1)
우선순위가 중간인 데이터를 삽입하는 과정에서 위치를 탐색해야 함 →
O(N)
Heap
데이터 삽입, 삭제 모두 →
O(log2N)
Heap
힙은 완전 이진 트리의 일종이다.
완전 이진 트리는 중복을 허용하지 않음, 힙은 중복을 허용함
모든 노드의 우선순위(노드의 값)은 자식 노드의 우선순위보다 크거나 같다
우선순위의 대소관계는 부모-자식 간에만 성립됨. 형제간에는 성립되지 않음
힙의 종류 : 최대 힙, 최소 힙
최대 힙 : 노드의 값이 클수록 우선순위가 높다, 루트노드의 값이 가장 크다
최소 힙 : 노드의 값이 작을수록 우선순위가 높다, 루트노드의 값이 가장 작다
힙의 삭제 과정
루트 노드를 삭제
마지막 노드를 루트 노드로 이동
Heapify 시작 (부모노드와 자식노드 중 큰 노드와 대소 비교)
힙의 삽입 과정
마지막 노드에 삽입
Heapify 시작 (부모노드와 자식노드의 대소 비교)
힙 자료구조는 대체적으로 배열로 구현된다.
완전 이진 트리를 기본으로 하기 때문에 빈 공간이 없어 배열로 구현하기 용이함
노드 번호가 i인 경우
부모 노드 :
arr[i // 2]
왼쪽 자식 노드 :
arr[2 * i]
오른쪽 자식 노드 :
arr[2 * i + 1]
최대 힙의 삽입, 삭제 과정
삽입 과정
삭제 과정
최소 힙 구현
Last updated