[우선순위 큐/힙]Heap이란?

 

힙관련 알고리즘 문제를 풀어보며 Heap에 대해 정확히 이해하고 넘어가자! 해서 정리하고자 한다.

힙(Heap)

---

 

자료구조에서 가장 큰 값, 작은 값 등을 빠르게 찾아내기 위한 Heap구조가 있다. 완전 이진 트리로 구성되었다.

이 Heap구조는 우선순위를 부여하여 가장 우선 순위가 높은 값부터 제거하는 우선순위 큐 를 구현하는 데 가장많이 쓰인다. Heap구조는 부모노드와 자식노드의 순서에만 관여하고 형제노드끼리의 순서와는 상관이 없다!

 

기본적으로 root 노드의 값이 가장 큰 MaxHeap과 root노드의 값이 가장 작은 MinHeap이 있다.

---

우선 트리의 구성방식을 보자!

 

root노드는 0인덱스가 아닌 1인덱스를 베이스로 한다.

왼쪽 자식노드 : 부모노드 * 2

오른쪽 자식노드 : 부모노드 * 2 +1

부모노드 : 자식노드 / 2

위처럼 노드 인덱스가 구성되기 때문에 계산을 위해 간편하게 root노드를 1부터 시작한다! 

 

노드들이 저렇게 구성되므로 트리의 높이 h는  log(n)이 된다! 예를들어 3개 노드가 있다면 2층짜리 트리가 완성되므로 h=2가 된다!

 

---

그렇다면 이제 Heap에 데이터를 insert할때와 delete할때 동작방식을 보자!

결과적으로 수행시간 시간복잡도는 최대로 트리의 높이만큼 검색하므로 O(log n)이된다.

 

 

● insert

 

MaxHeap insert 순서

MaxHeap의 isnert과정이다. Heap트리는 전체 트리 뿐 아니라 각각의 서브 트리도 Heap구조를 이뤄야한다.

insert순서

1.넣을 노드를 트리의 맨 끝부분에 삽입한다.

2.부모노드와 비교하며 각 서브트리마다 부모노드 > 삽입노드 인지 확인하고 아닐경우 부모노드와 자리를 바꾼다.

 

 

● delete

MaxHeap delete 순서

MaxHeap의 isnert과정이다. Heap트리는 전체 트리 뿐 아니라 각각의 서브 트리도 Heap구조를 이뤄야한다.

delete순서

1.root노드를 제거한다.

2.가장 마지막 끝의 노드를 root노드로 이동시킨다.

3.자식 노드들 중 큰 노드와 자리를 바꾼다.

 

구현 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeap {
	private ArrayList<Integer> heap;
	
	public MaxHeap(){
		heap = new ArrayList<>();
		heap.add(Integer.MAX_VALUE);//1부터 시작위해 0인덱스 채워줌
	}
	public void insert(int val){
		heap.add(val);
		int index = heap.size()-1;
        //마지막 노드에 삽입후 부모노드와 비교하며 자리변경
		while(index > 1 && heap.get(index/2)<heap.get(index)){
			int tmp = heap.get(index/2);
			heap.set(index/2, heap.get(index));
			heap.set(index, tmp);
			index=index/2;
		}
	}
	public int delete(){
		if(heap.size()-1 < 1){
			return 0;
		}
		//root노드
		int deleteVal = heap.get(1);
		heap.set(1, heap.get(heap.size()-1));
		heap.remove(1);
		
		int index=1;
        //자식노드가 있다면 계속 탐색
		while(index*2 < heap.size()){
			int max = heap.get(index*2);
			int maxIndex = index*2;
			
            //자식노드 2개중에 max값 찾음
			if((maxIndex+1) < heap.size() && max < heap.get(maxIndex+1)){
				max = heap.get(maxIndex+1);
				maxIndex = maxIndex+1;
			}
    		//max값보다 커서 변경할 노드가 없을경우 리턴
			if(heap.get(index) > max){
				return deleteVal;
			}
            //크기가 큰 자식노드와 자리변경
			int tmp = heap.get(index);
			heap.set(index, heap.get(maxIndex));
			heap.set(maxIndex, tmp);
			index = maxIndex;
			
		}
		return deleteVal;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		MaxHeap h = new MaxHeap();
		PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
		
		for(int i =0;i<10;i++){
			int val = Integer.parseInt(br.readLine());
			
			if(val == 0){
				System.out.println("heap : "+h.delete());
				System.out.println("priorityQueue : "+q.poll());
			}else{
				h.insert(val);
				q.add(val);
			}
			
			
		}
		
	}

}

 이해를 위해 직접 구현한 MaxHeap과 제공하는 Priority의 값이 같은걸 확인 할 수 있다. 사용하기 편리한 PriorityQueue자료구조를 많이 사용한다.