쉽게 배우는 자료구조 - Chap8.

KanuKim97·2023년 1월 17일
0

Data Structure with Java

목록 보기
5/6

힙(Heap)

우선순위 큐와 힙

우선순위 큐

우선순위를 부여하는 기준은 다양하지만,
우선순위 큐를 구현하는 대표적인 자료구조로 힙(Heap)이 있다.
우선순위를 가진 원소를 삽입할 수 있고,
우선순위가 가장 큰 원소를 빼내줄 수 있으면 우선순위 큐(Priority Queue)라고 한다.

우선순위 큐의 작업을 명시한 ADT(추상 데이터 타입)

원소를 삽입한다.
최대 원소를 알려주면서 삭제한다.
최대 원소를 알려준다.
우선순위 큐가 비어 있는지 확인한다.
우선순위 큐를 깨끗이 비운다.

힙과 완전 이진 트리

힙은 대표적인 우선순위 큐로, 완전 이진 트리(Complete Binary Tree)라는 구조를 사용한다.
트리(Tree)는 그래프 이론에서 "싸이클을 만들지 않는 연결된 그래프"로 정의된다.
이진 트리(Binary Tree)는 모든 노드가 2개 이하의 자식을 갖는 트리를 말한다.
포화 이진 트리(Full Binary Tree)는 루트로부터 시작해 모든 노드가 정확히 자식 노드를 2개씩 가지면서 꽉 채워진 트리를 말한다.
자식이 하나도 없는 노드를 리프 노드(Leaf Node) 또는 말단 노드(Terminal Node)라고 한다.
포화 이진 트리는 노드의 총 수가 1, 3, 7, 15, 31, ...과 같이 2k12^k -1개가 되어야 한다
노드의 수가 2k12^k -1개가 되지 못하는 경우 맨 왼쪽부터 차례로 채운 것이 완전 이진 트리이다.

[그림 1] 완전 이진 트리의 예

[그림 2] 포화 이진 트리의 예

힙의 조건

  1. 완전 이진 트리
  2. 힙 특성(Heap Property): 모든 노드는 값을 가지고, 자식 노드(들) 값보다 크거나 같다.

각 필드 작업의 의미

A[] // 힙을 저장하는 배열
numItems // 힙의 원소 수 저장

insert(x) // 힙에 원소 x를 삽입한다.
deleteMax() // 힙의 최대 원소를 알려주면서 삭제한다.
buildHeap() // 배열 A[]를 힙으로 만든다.
max() // 힙의 최대 원소를 알려준다.
isEmpty() // 힙이 비었는지 알려준다.
clear() // 힙에 깨끗이 정리한다.

힙의 구현

Heap.java

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(rightchild <= numItems-1 && A[child].compareTo(A[rightchild]) < 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;
	}
    
}

힙 수행시간

힙의 크기가 n인 경우,
힙 만들기 buildHeap()은 O(n) 시간이 든다.
힙에 원소를 삽입하는 작업 insert()는 A[n]에서 시작하는 percolateUp()가 전부이므로 O(logN)시간이 든다.
운이 좋으면 O(1)시간이 걸린다.
원소를 삭제하는 작업 deleteMax()는 A[0]에서 시작하는 percolateDown()이 전부이므로
O(logN)시간이 든다.
마찬가지로 운이 좋다면 O(1)시간이 걸린다.

profile
천방지축 개발자

0개의 댓글