참고
Heap Data Structure
NOTE
Heap ⇒ Binary heap을 의미하며, 모든 부모 노드가 자식 노드보다 크거나 같은 값을 갖는 완전 이진트리로, 최대값 또는 최소값을 효율적으로 조회할 수 있는 구조다!
최대 힙 → 가장 큰 원소가 루트 노드에 위치
최소 힙 → 가장 작은 원소가 루트 노드에 위치
완전 이진 트리(Complete Binary Tree)
NOTE
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있는 이진 트리!
순서대로 빈 노드없이 채워져있는 이진트리..
완전 이진트리는 배열로도 표현이 가능하다.
•
왼쪽 자식 노드 : array[2i + 1]
•
오른쪽 자식 노드 : array[2i + 2]
•
부모 노드 : array[(i - 1) / 2]
Heap Operation
Heapify
NOTE
Heapify ⇒ 배열로 표현되는 완전 이진트리가 있을 때, 임의의 노드를 루트로 하는 서브트리를 힙의 특성을 가지도록 재조정 하는 과정!
root를 4로 가지는 서브트리를 Heap으로 변경한다.
•
설명은 MaxHeap으로 진행한다.
•
array[3], array[4]를 먼저 힙으로 조정하는 과정이 있지만, 이미 되어있으므로 생략한다.
◦
조정 ⇒ 자식들 중 가장 큰 값이 루트보다 크면 스왑한다.
4의 자식들 (10, 5) → 10이 4보다 크므로 스왑한다.
1.
root(4)보다 자식 노드(10)이 더크므로 스왑한다.
2.
array[3]역시 자식 노드(9)가 더 크므로 스왑한다.
/**
* 리프노드가 아닌 최초의 노드에서 맨 끝 노드 array[n-1]의
* 부모인 array[(n-2)/2]에서부터 array[0]까지 heapify()를 반복합니다.
*/
public void Heapify() {
// // array[n-1] -> array[n-2] -> .. -> array[0]
for (int i = (n - 2) / 2; i >= 0; i--) {
bubbleDown(i);
}
}
Java
복사
간단한 코드 구현 (재귀방식)
Heap - push
NOTE
배열의 맨 끝 위치인 array[n]에 추가하고, 힙의 특성을 만족시키기 위해 상위 노드로 이동하며 힙을 조정한다!
상위 노드로 가면서 heapify
push(int n){
int i = array.length;
arr[size] = n;
int parent = (i-1) / 2;
while(i > 0 && arr[i] arr[parent]){
swap(arr[i], arr[parent];
i = parent;
parentIdx = (i-1)/2;
}
}
Java
복사
while문 구현
bubbleUp(int i){
int parent = (i-1)/2;
if(arr[i] > parent[i]) {
swap(arr[i], parent[i]);
bubbleUp(parrent);
}
}
Java
복사
재귀 구현
Heap - pop
NOTE
Max Heap ⇒ root가 항상 가장 큰 값이다!
20을 pop하고 가장 마지막의 값을 root로 올린다.
bubbleDown(int n, int heapSize){
int root = n;
int left = n*2 + 1;
int right = n*2 + 2;
if(left < heapSize && arr[left] > arr[root]) root = left;
if(right < heapSize && arr[right] > arr[root]) root = right;
if(root != i){
swap(i, root);
Heapify(root);
}
}
Java
복사
heapify 방식( 위 → 아래 )
우선순위 큐(Priority Queue)
NOTE
우선순위 큐 ⇒ 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나간다!
message queue에서도 사용됨
public class StreamingRequest implements Comparable<StreamingRequest> {
String userId;
SubscriptionType subscriptionType;
public StreamingRequest(String userId, SubscriptionType subscriptionType) {
this.userId = userId;
this.subscriptionType = subscriptionType;
}
@Override
public int compareTo(StreamingRequest o) {
return this.subscriptionType.priority - o.subscriptionType.priority;
}
@Override
public String toString() {
return "Processed request from user " + userId + " with subscription type " + subscriptionType;
}
}
Java
복사
StreamingRequest 객체
public enum SubscriptionType {
BASIC(1),
PREMIUM(2);
final int priority;
SubscriptionType(int priority) {
this.priority = priority;
}
}
Java
복사
구독 타입
구독 유형에 따른 우선순위를 위한 PriorityQueue
NOTE
public class PriorityQueue {
private StreamingRequest[] array;
private int n;
public PriorityQueue(int n) {
this.array = new StreamingRequest[n];
this.n = 0;
}
public void push(StreamingRequest e){
if(n == array.length) throw new IndexOutOfBoundsException();
array[n] = e;
bubbleUp(n++);
}
private void bubbleUp(int i){
int parent = (i-1)/2;
if(parent >= 0 && array[i].compareTo(array[parent]) > 0){
swap(i, parent);
bubbleUp(parent);
}
}
public StreamingRequest pop(){
if(n==0) throw new RuntimeException("heap empty");
StreamingRequest max = array[0];
swap(0, n-1);
n--;
bubbleDown(0);
return max;
}
private void bubbleDown(int i){
int root = i;
int leftChild = i*2 + 1;
int rightChild = i*2 + 2;
if(leftChild < n && array[leftChild].compareTo(array[i]) > 0) root = leftChild;
if(rightChild < n && array[rightChild].compareTo(array[i]) > 0) root = rightChild;
if(root != i){
swap(i, root);
bubbleDown(root);
}
}
private void swap(int i, int j) {
StreamingRequest temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public void build() {
for (int i = (n - 2) / 2; i >= 0; i--) {
bubbleDown(i);
}
}
}
Java
복사
대부분 Heap구조에서 설명한 함수
StreamingRequest 객체
NOTE
public class RequestHandler {
PriorityQueue pq = new PriorityQueue(100);
public void addRequest(StreamingRequest request){
pq.push(request);
}
public StreamingRequest getNestRequestToProcess(){
return pq.pop();
}
public static void main(String[] args) {
RequestHandler requestHandler = new RequestHandler();
requestHandler.addRequest(new StreamingRequest("user1", SubscriptionType.BASIC));
requestHandler.addRequest(new StreamingRequest("user2", SubscriptionType.PREMIUM));
requestHandler.addRequest(new StreamingRequest("user3", SubscriptionType.BASIC));
requestHandler.addRequest(new StreamingRequest("user4", SubscriptionType.PREMIUM));
requestHandler.addRequest(new StreamingRequest("user5", SubscriptionType.PREMIUM));
for (int i = 0; i < 5; i++) {
StreamingRequest nextRequest = requestHandler.getNestRequestToProcess();
System.out.println(nextRequest);
}
}
}
Java
복사
Premium, Basic 우선순위값 할당
Premium이 먼저함.. (기본은 나가라)