CamelAct

Overview

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조입니다.

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현합니다.

부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진트리입니다.

삽입 또는 삭제 연산을 위한 시간 복잡도는 O(n)입니다.

반면 힙트리는 완전 이진트리 구조이므로 힙트리의 높이는 log₂(n+1)이며, 힙의 시간 복잡도는 O(log₂n)입니다.

자식 노드를 구하고 싶을 때

  - 왼쪽 자식 노드 index = (부모 노드 index) * 2

  - 오른쪽 자식 노드 index = (부모 노드 index) * 2 + 1

부모 노드를 구하고 싶을 때

  - 부모 노드 index = (자식 노드 index) / 2

Usecase

  - 명품 스토어 대기열에 명단을 넣는데 VVIP라면 먼저 거래할 수 있도록 한다.

Structure

Code Example

package com.algorithm.basic;

public class PriorityQueue {
	final int MAX_SIZE = 1000;

	int heap[] = new int[MAX_SIZE];
	int heapSize = 0;

	void init() {
		heapSize = 0;
	}

	void push(int value) {
		if (heapSize + 1 > MAX_SIZE) {
			return;
		}

		heap[heapSize] = value;

		int current = heapSize;
		while (current > 0 && heap[current] < heap[(current - 1) / 2]) {
			int temp = heap[(current - 1) / 2];
			heap[(current - 1) / 2] = heap[current];
			heap[current] = temp;
			current = (current - 1) / 2;
		}

		heapSize = heapSize + 1;
	}

	int pop() {
		if (heapSize <= 0) {
			return -1;
		}

		int value = heap[0];
		heapSize = heapSize - 1;

		heap[0] = heap[heapSize];

		int current = 0;
		while (current < heapSize && current * 2 + 1 < heapSize) {
			int child;
			if (current * 2 + 2 >= heapSize) {
				child = current * 2 + 1;
			} else {
				child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
			}

			if (heap[current] < heap[child]) {
				break;
			}

			int temp = heap[current];
			heap[current] = heap[child];
			heap[child] = temp;

			current = child;
		}
		return value;
	}

	void print(int[] heap, int heap_size) {
		for (int i = 0; i < heap_size; i++) {
			System.out.print(heap[i] + " ");
		}
		System.out.println();
	}

	public static void main(String arg[]) throws Exception {
		PriorityQueue priorityQueue = new PriorityQueue();
		
		int N = 10;

		priorityQueue.init();

		priorityQueue.push(1);
		priorityQueue.push(3);
		priorityQueue.push(6);
		priorityQueue.push(5);
		priorityQueue.push(2);
		priorityQueue.push(7);
		priorityQueue.push(4);
		priorityQueue.push(8);
		priorityQueue.push(9);
		priorityQueue.push(0);

		for (int i = 0; i < N; i++) {
			System.out.print(priorityQueue.pop() + " ");
		}
		System.out.println();
	}
}

Console Result

0 1 2 3 4 5 6 7 8 9

Conclusion

N/A