힙 Heap : 배열을 이용해 구현한 우선순위큐, 전위순회

1. 힙이란?

데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전이진트리(Complete Binary Tree)이다.

-완전이진트리 : 노드를 삽입할때 왼쪽노드부터 차례대로 삽입하는 트리

 

힙을 사용하는 이유

• 배열에 데이터를 넣고 최대값, 최소값을 찾으려면 O(N)이 걸린다.
• 이에 반해, 힙에 데이터를 넣고 최대값,최소값을 찾으려면 O(1)이 걸린다.
• 우선순위큐와 같이 최대값과 최소값을 빠르게 찾아야하는 자료구조와 알고리즘 구현등에 사용된다.

 

2. 힙의 두가지 조건

• 각 노드의 값은 자식노드가 가진 값보다 크거나 같다. (최소힙의 경우 자식노드가 가진 값보다 작거나 같다)
• 완전 이진 트리 형태를 가진다.

3. 힙과 이진탐색트리의 공통점과 차이점

공통점 : 힙과 이진탐색트리는 이진트리이다.

차이점 :

힙은 각 노드의 자식노드보다 크거나 같다.(작거나 같다) 하지만 이진탐색트리는 왼쪽자식노드값보다 크고, 오른쪽 자식보다 작다.

이진탐색트리는 탐색을 위한 구조, 힙읍 최대값/최소값 검색을 위한 구조라고 이해하면 된다.

 

4. 힙 시간 복잡도

n개의 노드를 가지는 힙에 데이터 삽입, 삭제 시 최악의 경우 root노드부터 leaf노드까지 비교해야하므로 O(logn)이다.

 

5. 부모노드, 자식노드 

// 부모노드의 인덱스 반환 (부모노드 index = 자식노드 / 2)
    private int parent(int pos) { return pos / 2; } 
  
    // 왼쪽노드 위치 반환
    private int leftChild(int pos) { 
    	return (2 * pos); 
    } 
    
    // 오른쪽노드 위치 반환
    private int rightChild(int pos) 
    { 
        return (2 * pos) + 1; 
    } 
  
    // Leaf Node(자식노드가 없는)이라면 true, 있다면 false
    private boolean isLeaf(int pos) 
    { 
        if (pos > (size / 2) && pos <= size) { 
            return true; 
        } 
        return false; 
    } 

최대힙 구현 자바 코드

public class MaxHeap { 
    private int[] Heap; 
    private int size; //Heap 배열의 요소 개수
    private int maxsize; //최대 이진트리 요소의 개수
  
    public MaxHeap(int maxsize) 
    { 
        this.maxsize = maxsize;
        this.size = 0; 
        Heap = new int[this.maxsize + 1];
        Heap[0] = Integer.MAX_VALUE;  //2147483647
        //Heap배열은 편의를 위해 인덱스 1번부터 시작한다. 
    } 

    public void insert(int element) 
    { 
    	int i; //히프 크기 마지막 인덱스
    	
    	size++;
    	i = size;
    	while (i != 1 && element > Heap[i / 2]) {
    		Heap[i] = Heap[i / 2];
    		i /= 2;
    	}
    	Heap[i] = element;
    } 
  
    public void print() 
    { 
        for (int i = 1; i <= size / 2; i++) { 
            System.out.print( 
                " PARENT : " + Heap[i] 
                + " LEFT CHILD : " + Heap[2 * i] 
                + " RIGHT CHILD :" + Heap[2 * i + 1]); 
            System.out.println(); 
        } 
    } 
  
    // 최대값(root)를 추출한다.(제거 및 반환)
    public int extractMax() 
    { 
    	int item = Heap[1];
    	int temp;
    	int p;
    	int c;
    	
    	temp = Heap[size--];
    	
    	p = 1;
    	c = 2;
    	while (c <= size) {
    		if (c < size && Heap[c] < Heap[c + 1]) {
    			c++;
    		}
    		
    		if (Heap[c] <= temp) {
    			break;
    		} else {
    			Heap[p] = Heap[c];
    			p = c;
    			c *= 2;
    		}
    	}
    		Heap[p] = temp;
    		return item;
    } 
  
    public static void main(String[] arg) 
    { 
        System.out.println("The Max Heap is "); 
        MaxHeap maxHeap = new MaxHeap(15); 
        maxHeap.insert(5); 
        maxHeap.insert(3); 
        maxHeap.insert(17); 
        maxHeap.insert(10); 
        maxHeap.insert(84); 
        maxHeap.insert(19); 
        maxHeap.insert(6); 
        maxHeap.insert(22); 
        maxHeap.insert(9); 
  
        maxHeap.print(); 
        System.out.println("The max val is "
                           + maxHeap.extractMax()); 
    } 
}

힙에서의 전위순회 구현 자바 코드

public void preorder(int root) {
    	if (root <= size) {
    		System.out.println(Heap[root]);
    		preorder(root * 2); //왼쪽자식노드로
    		preorder(root * 2 + 1); //오른쪽 자식 노드로
    	}
    }

힙에서의 데이터 찾기 자바 코드

public int find(int root, int key) {
    	if (root > size) return 0; //힙 안에 key가 없음.
    	
    	if (Heap[root] == key) {
    		return root;
    	} else if (Heap[root] < key) {
    		return 0;
    	} else {
    		return Math.max(find((root * 2), key), find((root * 2 + 1), key));
    	}
    }

 

추가학습

Math.max()함수는 입력받은 두 인자 중 큰 값을 리턴하는 함수이다.