Data Structure - 우선순위 큐(priority queue), 힙(heap)

안녕하세요.

공상 개발입니다.

 

이번 시간에는 우선순위 큐(priority queue)와 힙(heap)에 대해 알아보는 시간을 갖겠습니다.

 

---

 

1. 우선순위 큐 (priority queue) 개념 2. 힙(heap) 개념 3. upheap, downheap 연산 4. LPT(longest processing time first)

 

---

 

# 우선순위 큐 (priority queue) 개념

 

• 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조입니다.
• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.
• 응용분야 : 네트워크 트래픽 제어, 운영 체제에서의 작업 스케줄링.

자료구조	삭제되는 요소
스택	가장 최근에 들어온 데이터
큐	가장 먼저 들어온 데이터
우선순위큐	가장 우선순위가 높은 데이터

• 우선순위 큐를 구현하는 방법은 다양합니다.
•  - 1) 리스트를 이용하여 구현할 수 있습니다.
•  - 2) 힙(heap)을 이용하여 구현할 수 있습니다.
•  - 3) 배열을 이용하여 구현할 수 있습니다.

 

• 데이터의 개수가 N 개일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 다음과 같습니다.
• 위의 조건으로 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬)

표현 방법	삽입	삭제
순서없는 배열	O(1)	O(n)
순서없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
히프	O(logn)	O(logn)

 

---

 

# 힙(heap) 개념

 

• 힙은 완전 이진 트리 자료구조의 일종입니다.
• 힙에서는 항상 루트 노드(root node)를 제거합니다.

 

 

• 최대 힙(max heap), 값이 큰 데이터가 우선적으로 제거됩니다.
• 최소 힙(min heap), 값이 작은 데이터가 우선적으로 제거됩니다.

 

완전 이진 트리(Complete Binary Tree)란 루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미합니다.

 

 

단순히 힙을 배열로 구현하는 방법은 어렵지 않습니다.

 

 

바로 코드로 보겠습니다.

 

 

---

 

# upheap, downheap 연산

 

 upheap : 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드에 이어서 삽입합니다.

• 삽입 후에 새로운 노드를 부모 노드들과 교환해서 히프의 성질을 만족

 

upheap 연산 1

upheap 연산 2

 

 

 

---

downheap : 최대 힙에서의 삭제는 가장 큰 키값을 가진 노드를 삭제하는 것을 의미합니다.
→ 따라서 루트 노드가 삭제됨

 

1. 루트 노드를 삭제

2. 마지막 노드를 루트 노드로 이동

3. 루트에서부터 단말 노드까지의 경로에 있는 노드들을 교환하여 히프 성질을 만족시키도록 변경

 

downheap 연산 1

downheap 연산 2

 

 

힙(heap)의 복잡도 분석 삽입 연산에서 최악의 경우, 루트 노드까지 올라가야 하므로 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요  삭제도 최악의 경우, 가장 아래 레벨까지 내려가야 하므로 역시 트리의 높이 만큼의 시간이 필요

 

---

 

# LPT(longest processing time first)

 

머신 (machine) 스케줄링

조건 • 기계가 (서버가) m 개, 처리해야 할 작업이 n 개 • 각 작업이 필요로 하는 기계의 사용 시간은 각각 다름 • 모든 기계를 풀가동하여 가장 최소의 시간 안에 작업들을 모두 끝내는 것

 

머신 (machine) 스케줄링을 위한 다양한 알고리즘이 존재합니다.

그중 하나의 방법이 LPT (longest processing time first) 있는데, 이 방법은 가장 긴 작업을

종료시간이 최소인 기계에 우선적으로 할당하는 방법입니다.

 

 

---

 

피드백

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시면 감사하겠습니다.

 

읽어주셔서 감사합니다.