[ 알고리즘 ] 우선순위 큐 (1) - 배열

@ 왜 궁금했는가? 

요즘 알고리즘 공부하는데,, 우선순위 큐 문제가 자주 출제 되서 한번 정리하고 싶은 생각에 !!!

 

---

@ 공부

우선 순위 큐란?

- 큐 자제가 들어간 순서대로 나오는것인데 우선순위 큐는 값에 따라서 가장 큰 우선순위인 값이 나온다.

 

예)

일반 큐

(2)-(3)-(4)-(5)

: pop() 하면 2가 나온다.

우선 순위 큐

(2)-(3)-(4)-(5)

: pop() 하면 5가 나온다.

 

@ 구현

## 배열로 구현

4 5 3 2 1

pop : 5

4 [ ] 3  2 1

앞 공간 채워 줘야 한다.

4 3 2 1 

 

Push: O(1)

Pop: O(n) > 누가 우선 순위가 가장 큰지 확인하고 다 땡겨 주는데 O(2N) 이므로 O(N) 이 됩니다.

 

- 구현

public class PriorotyQue {
	public static void main(String[] args) {
		PriorityQueue myQu = new PriorityQueue();
		myQu.push(1);
		myQu.push(8);
		myQu.push(7);
		myQu.push(5);
		System.out.println(myQu.top()); // 8
		
		myQu.pop();
		System.out.println(myQu.top()); // 7

		myQu.pop();
		System.out.println(myQu.top()); // 5
		
		myQu.pop();
		System.out.println(myQu.top()); // 1
		//overFlow
		//underFlow 는 생략
	}
}

class PriorityQueue {
	int Max = 100;
	int[] data = new int[Max];
	int len = 0;

	void push(int x) {
		data[len++] = x;
	}

	void pop() {
		int myMax = -91292389, myMaxInx = -1;
		for (int i = 0; i < len; i++) {
			if (data[i] > myMax) {
				myMax = data[i];
				myMaxInx = i;
			} // 가장 큰 값이 어디 있는지 구하기 위해서
		}

		for (int i = myMaxInx; i < len; i++) {
			data[i] = data[i + 1];
		} // 다 앞으로 땡겨주고
		len--;
	}

	int top() {
		int myMax = -328942;

		for (int i = 0; i < len; i++) {
			if (data[i] > myMax) {
				myMax = data[i];
			}
		}
		return myMax;
	}
}

 

## 배열을 이용한 우선순위 큐의 비효율성

for(int i= 100000 ;i>=1;i--){
	myQu.push(i);
}

for(int i=1 ;i <= 100000 ;i++){
	myQu.pop(); 
}
// O(N) 을 100000 번씩 하니까 O(n^2) 만큼 걸린다.

정말 엄청 비효율적

 

## 트리로 구현