우선순위 큐와 힙(Heap)

thsamajiki·2023년 1월 17일

자료구조

목록 보기

8/8

우선순위 큐(Priority Queue)

일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

우선순위 큐를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

Comparable Interface를 구현하면 compareTo 메소드를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue가 알아서 우선순위가 높은 객체를 추출해준다.

우선순위 큐를 구현하는 대표적인 자료구조로 힙(Heap)이 있다.
우선순위 큐는 Heap을 이용하여 구현하는 것이 일반적이다.

힙(Heap)

우선순위 큐의 목적인 우선순위를 가진 원소를 삽입하고 삭제하는 것을 아주 효율적으로 다룰 수 있는 자료구조이다.

힙은 완전 이진 트리(Complete Binary Tree) 구조를 사용한다. 완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다.

힙의 조건은 아래와 같다.

완전 이진 트리
모든 노드는 값을 갖고, 자식 노드 값보다 크거나 같다.

힙의 특성

완전 이진 트리를 배열로 표현할 수 있다. 완전 이진 트리를 기본으로 하기 때문에 비었는 공간이 없어 배열로 구현하기에 용이하다.
다음 그림과 같이, 루트 노드를 배열의 0번 index에 저장하고, 각 노드를 기점으로 왼쪽 자식노드는 a[i∗2+1], 오른쪽 자식노드는 a[i∗2+2] 의 index에 저장된다. 또한 특정 index의 노드에서 부모노드는 a[(i−1)//2]로 찾을 수 있다.

부모 노드, 자식 노드 계산법

PriorityQueueInterface

public interface PQInterface<E> {
	public void insert(E newItem) throws Exception;
	public E deleteMax() throws Exception;
	public E max() throws Exception;
	public boolean isEmpty();
	public void clear();
}

PQException(예외 클래스 선언)

public class PQException extends Exception {
	public PQException(String msg) {
		super(msg);
	}
}

Heap(힙 구현)

package heap;

public class Heap<E extends Comparable> implements PQInterface<E> {
	private E[] A;
    private int numItems;
    
    public Heap(int arraySize) {
    	A = (E[]) new Comparable[arraySize];
        numItems = 0;
    }
    
    public Heap(E[] B, int numElements) {
    	A=B; //배열 레퍼런스 복사
        numItems = numElements;
    }
    
    // 힙에 원소 삽입하기 (재귀 ver.)
    public void insert(E newItem) throws PQException {
    // 힙 A[0...numItems-1]에 원소 newItem을 삽입한다.(추가한다)
    	if(numItems < A.length) {
        	A[numItems] = newItem;
            percolateUP(numItems);
            numItems++;
    	} else throw new PQException("Heap Err: Insert() - Overflow!");
    }
    
    // 스며오르기 percolateUp()
	public void percolateUp(int i) {
    	// A[i]에서 시작해서 힙 성질을 만족하도록 수선한다.
		// A[0...i-1]은 힙 성질을 만족하고 있음
        int parent = (i-1)/2;
		if (parent >= 0 && A[i].compareTo(A[parent])>0) {
			E temp = A[i];
			A[i] = A[parent];
			A[parent] = temp;
			percolateUp(parent);
		}
	}

	// 힙에서 원소 삭제하기
	public E deleteMax() throws Exception {
    	// 힙 A[0...numItems-1]에서 최대값을 삭제하면서 리턴한다.
		if(!isEmpty()) {
			E max =A[0]; 
			A[0] = A[numItems-1];
			numItems--;
			percolateDown(0);
			return max;
		}else throw new PQException("HeapErr: DeleteMax()-Underflow");
	}
	
    // 스며내리기 percolateDown()
	public void percolateDown(int i) {
    	// A[0...numItems-1]에서 A[i]를 루트로 스며내리기
		int child = (2*i)+1; //왼쪽 자식
		int rightchild = (2*i)+2; //오른쪽 자식
		if(child<=numItems-1) {
			if(rchild <= numItems-1 && A[child].compareTo(A[rchild]) < 0) {
				child = rightchild; // 더 큰자식의 인덱스
			}
			if(A[i].compareTo(A[child])<0) {
				E temp = A[i];
				A[i] = A[child];
				A[child] = temp;
				percolateDown(child);
			}
		}
	}
	
    // 힙으로 만들기
	public void buildHeap() {  
		if(numItems >= 2) {
			for(int i =(numItems-2)/2 ; i>= 0 ; i--) { percolateDown(i); }
		}
	}
	
	힙의 최대값 구하기
	public E max() throws Exception {
		if(!isEmpty()) {
			return A[0];
		}else throw new PQException("HeapErr: Max()-Empty!");
	}

	// 힙이 비어있는지 확인하기
	public boolean isEmpty() {
		return numItems == 0;
	}

	// 힙 비우기
	public void clear() {
		A = (E[]) new Comparable[A.length];
		numItems = 0;
	}
    
}