[Java] 힙 (Heap)

1. 힙

• 여러 개의 값들 중에서 최대값이나 최소값을 빠르게 찾기 위해 만들어진 자료구조
• 완전 이진 트리의 일종으로 주로 우선순위 큐에 사용됨
• 이진 탐색 트리와 달리 힙 트리에서는 중복된 값을 허용하지 않음
• 힙은 부모 노드의 값이 자식 노드의 값보다 항상 큰(작은) 느슨한 정렬 상태를 유지하는 이진 트리
• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리는 최대 힙(max heap), 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리는 최소 힙(min heap)

 

2. 힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이며 첫 번째 index 0은 편의를 위해 사용하지 않음
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음
• 힙에서 parents와 child의 관계 (index)

leftChild = parents * 2
rightChild = parents * 2 + 1
parents = child / 2

 

 

3. 힙의 삽입

1. 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입
2. 새로운 노드를 부모 노드와 비교하며 교환해서 힙의 성질을 만족시킴

Example (최대 힙)

(a) index 순으로 마지막 위치 뒤에 새로운 요소 8 삽입

(b) 삽입 노드 8 > 부모 노드 4 => 교환

(c) 삽입 노드 8 > 부모 노드 7 => 교환

(d) 삽입 노드 8 < 부모 노드 9 => 교환하지 않고 삽입 완료

 

4. 힙의 삭제

1. 최대 힙에서 삭제 연산은 최댓값을 삭제하는 것이므로 루트 노드 삭제
2. 삭제된 루트 노드 위치에 힙의 마지막 노드를 가져옴
3. 힙을 재구성

Example (최대 힙)

(a) 최대값인 루트 노드 9를 삭제하고 마지막 노드를 가져옴

(b) 삽입 노드 3 < 자식 노드 7 => 교환

(c) 삽입 노드 3 < 자식 노드 5 => 교환

(d) 삽입 노드 3 > 자식 노드 1, 2 => 교환하지 않고 삽입 완료

 

5. Java로 구현한 힙

최대 힙 (Max heap)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class maxHeap {
	private ArrayList<Integer> heap;
    
    // 힙 생성자
    public minHeap() {
    	heap = new ArrayList<>();
        heap.add(1000000);	// index 0을 채우고 1부터 시작
        // 삽입 단계에서 자식 노드와 swap 되지 않도록 큰 수를 넣음
    }
    
    // 삽입
    public void insert(int key) {
    	heap.add(key);
        int curr = heap.size() - 1;	// 마지막 노드부터 탐색 시작
        
        // root까지 이동하며 삽입된 요소의 자리 교체
        while(curr > 1 && heap.get(curr / 2) < heap.get(curr)) {
        	System.out.println("swap");
            
            // 자식 노드가 부모 노드보다 크면 swap
            int temp = heap.get(curr / 2);
            heap.set(curr/2, haep.get(curr));
            heap.set(curr, temp);
            
            curr = curr / 2;
         }
	}
     
	// 삭제
	public int delete() {
     	
		// 힙이 비어 있을 경우 종료
        if(heap.size()-1 < 1) {
         	return 0;
        }
        
        // 삭제할 노드를 루트 노드로 설정
        int deleteItem = heap.get(1);
        
        // root를 가장 마지막 노드 값으로 교체하고 마지막 값 삭제
        heap.set(1, heap.get(heap.size()-1));
        heap.remove(heap.size()-1);
        
        int index = 1;	// 루트 노드에서 시작하여 재구성
        
        // root부터 시작하여 마지막 노드까지 탐색
        while((index*2) < heap.size()) {
        	int max = heap.get(index*2);	// 최대값을 leftChlid의 key 값으로 초기화
            int maxIndex = index * 2;	// 최대값의 위치를 leftChild의 index 값으로 초기화
            
            // rightChild가 존재하며 그 값이 leftChild보다 클 경우
            if((index*2 + 1) < heap.size() && max < heap.get(index*2 + 1)) {
                max = heap.get(index*2 + 1);	// 최대값을 rightChild의 key 값으로 초기화
                maxIndex = index*2 + 1;	// 최대값의 위치를 rightChild의 index 값으로 초기화
            }
            
            // 부모 노드(=재구성할 노드)가 자식 노드보다 크면 재구성 완료
            if(heap.get(index) > max) {
            	 break;
            }
            
            // 부모 노드가 자식 노드보다 작으면 swap
            int temp = heap.get(index);
            heap.set(index, heap.get(maxIndex));
            heap.set(maxIndex, temp);
            index = maxIndex;
		}
        
        return deleteItem;
	}
    
    // 노드 개수 num을 입력받은 후, 각 노드의 key 값을 모두 입력 받아 힙을 생성
    public static void main(String[] args) {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int num = Integer.parseInt(br.readLine());
        maxHeap heap = new maxHeap();
        
        for(int i = 0; i < num; i++) {
        	int key = Integer.paresInt(br.readLine());
            
            if(key == 0) {
            	System.out.println(heap.delete());
			} else {
            	heap.insert(key);
			}
		}
	}
}