[자료구조]힙(Heap), 우선순위 큐

힙

차곡차곡 쌓아 올린 더미

루트노드로 갈 수록 값이 커지면 최대 힙

루트노드로 갈 수록 값이 작아지면 최소 힙

최대 힙, 최소 힙 둘 다 우선순위에 맞게 데이터를 저장하고 삭제한다

힙은 우선순위 큐 구현에 어울리는 완전 이진 트리의 일종이다

 

힙 구현

 

저장과 삭제 연산

• 힙은 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하기 때문에 연결 리스트로 구현 하게되면 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다 그래서 배열로 구현해야 한다
• 배열로 구현 시 배열의 인덱스가 0인 위치는 사용하지 않고 노드의 고유번호에 맞게 편의성을 준다
• 왼쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 * 2
• 오른쪽 자식 노드의 인덱스 값 = 부모 노드의 인덱스 값 * 2 + 1
• 부모 노드의 인덱스 값 = 자식 노드의 인덱스 값 / 2 (정수 값)

 

 

저장 연산

 

1. 우선순위가 제일 낮다는 가정하에서 마지막 위치에 저장
2. 부모노드와 우선순위를 비교해서 위치 변경
3. 맞는 위치를 찾을 때까지 반복

삭제 연산

 

1. 삭제 시 우선순위가 높은 루트노트부터 삭제하면 우선순위 큐가 된다
2. 삭제한 루트노트에 마지막 노드를 넣는다
3. 루트노드로 간 마지막 노드를 왼쪽 자식과 오른쪽 자식과 비교해 우선순위가 높은 노드와 위치 변경
4. 맞는 위치를 찾을 때까지 반복

 

python

 

우선순위 큐

일반적으로 큐에 데이터를 삽입하고 먼저 삽입된 것을 꺼내는 작업에서

우선순위를 정해서 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다

예를 들어 응급상황과 같다

우선순위 큐의 구현

배열과 연결 리스트로 우선순위 큐를 구현하면 데이터를 삽입 및 삭제하는 과정에서 데이터를 뒤로 밀거나 앞으로 당기는 연산이 추가된다

또한 삽입 위치를 찾기 위해 모든 노드를 비교해야 하는 경우도 생긴다

이러한 성능 저하 문제를 해결하기 위해

자료구조 힙으로 구현하는 우선순위 큐가 성능이 좋다

힙의 저장, 삭제 연산으로 우선순위 큐를 빠르게 구현할 수 있다

 

python