힙(Heap)

힙이란?

• 완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 일반적으로 힙은 최대 힙을 의미
• 같은 키값의 노드 중복 가능

 

최대 힙(Max Heap)

• 키 값이 가장 큰 노드를 찾기 위한 힙
• 부모 노드의 키값 >= 자식 노드의 키값

 

최소 힙(Min Heap)

• 키 값이 가장 작은 노드를 찾기 위한 힙
• 부모 노드의 키값 <= 자식 노드의 키값

 

출처: andrew.cmu.edu

 

순차 자료구조를 이용한 최대 힙 구현

• 부모노드 인덱스 = 자식노드 인덱스 / 2

public class HeapMadyByArrayList {
    public static void main(String[] args) {
        Heap heap = new Heap();
        heap.insertHeap(6);
        heap.insertHeap(4);
        heap.insertHeap(2);
        heap.insertHeap(10);
        heap.insertHeap(7);
        heap.insertHeap(3);
        heap.printHeap();

        int heapSize = heap.getHeapSize();
        for (int i = 1; i <= heapSize; i++) {
            int deletedItem = heap.deleteHeap();
            System.out.printf("\nDeleted Item: [%d] ", deletedItem);
        }
    }
}

class Heap {
    private int heapSize;
    private int itemHeap[];

    public Heap() {
        heapSize = 0;
        itemHeap = new int[50];
    }

    public void insertHeap(int item) {
        int i = ++heapSize;
        while ((i != 1) && (item >= itemHeap[i/2])) {
            itemHeap[i] = itemHeap[i/2];
            i = i/2;
        }
        itemHeap[i] = item;
    }

    public int deleteHeap() {
        int item = itemHeap[1];
        int temp = itemHeap[heapSize--];
        int parent = 1;
        int child = 2;

        while (child <= heapSize) {
            if ((child < heapSize) && (itemHeap[child] < itemHeap[child+1])) {
                child++;
            }
            if (temp >= itemHeap[child]) break;

            itemHeap[parent] = itemHeap[child];
            parent = child;
            child = child * 2;
        }
        itemHeap[parent] = temp;
        return item;
    }

    public int getHeapSize() {
        return this.heapSize;
    }

    public void printHeap() {
        System.out.println("PrintHeap >>>");
        for (int i = 1; i <= heapSize; i++) {
            System.out.printf("[%d] ", itemHeap[i]);
        }
    }
}

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음