자료구조 - Heap

Heap

---

Heap

• 완전 이진 트리이며 최대, 최소값만을 필요로 할 때 적합한 자료구조이다.

• 시간복잡도- 요소의 개수가 n개일때 삽입, 삭제시 트리의 높이 만큼 소요된다.

  1. insert: O(nlogn)

  2. delete: O(nlogn)

 

구현 with JAVA

• 최대힙

public class maxHeap{
    private int[] heap;
    private int idx;
    private int size;
 
    //생성자
    public maxHeap(int size) {
        this.idx = 0;
        this.size = size;
        maxHeap = new int[size];
    }
 
    public boolean isEmpty() {
        return idx == 0
    }
 
    public boolean isFull()    {
        return idx == size;
    }
 
    //힙에 데이터 insert. 우선 맨 마지막 위치에 data를 삽입한 후 부모 노드와 값을 비교하면 자리를 찾는다
    public void insert(int data) {
        if(isFull()) return;
        else {        
            maxHeap[++idx] = data;
            int index = idx;
            while(index > 1 && (maxHeap[index] > maxHeap[index / 2]) { //부모 노드의 값이 더 작은 경우 부모와 자리를 바꾼다.
                int temp = maxHeap[index];
                maxHeap[index] = maxHeap[index / 2];
                maxHeap[index / 2] = temp;
                index = index / 2;
            }
        }
    }
 
    //힙의 데이터 delete. 루트의 데이터를 삭제한 후 반환하고, 루트에는 맨 마지막 위치의 데이터를 넣어준다.
    public int delete() {     
        if(isEmpty()) return;
        else {
            int root = maxHeap[1];
            maxHeap[1] = maxHeap[idx];
            maxHeap[idx--] = 0;
            maxHeapify(); //다시 재정렬한다.
            return root;
        }
    }
 
//최대힙 정렬
    public void maxHeapify() {
        int index = 1;
        int temp;    
 
        while(index * 2 <= idx) {
            if(maxHeap[index * 2] > maxHeap[index * 2 + 1]) { //왼쪽 자식의 값이 더 큰경우
                temp = maxHeap[index];
                maxHeap[index] = maxHeap[index * 2];
                maxHeap[index + 2] = temp;
                index = index * 2;    
            } else { //오른쪽 자식의 값이 더 큰경우
                temp = maxHeap[index];
                maxHeap[index] = maxHeap[index * 2 + 1];
                maxHeap[index + 2 + 1] = temp;
                index = index * 2 + 1;    
            }
        }
    }
}
 

 

• 최소힙

public class minHeap{
    private int[] heap;
    private int idx;
    private int size;
 
    //생성자
    public minHeap(int size) {
        this.idx = 0;
        this.size = size;
        minHeap= new int[size];
    }
 
    public boolean isEmpty() {
        return idx == 0
    }
 
    public boolean isFull()    {
        return idx == size;
    }
 
    //힙에 데이터 insert. 우선 맨 마지막 위치에 data를 삽입한 후 부모 노드와 값을 비교하면 자리를 찾는다
    public void insert(int data) {
        if(isFull()) return;
        else {        
            minHeap[++idx] = data;
            int index = idx;
            while(index > 1 && (minHeap[index] < minHeap[index / 2]) { //부모 노드의 값이 더 큰 경우 부모와 자리를 바꾼다.
                int temp = minHeap[index];
                minHeap[index] = minHeap[index / 2];
                minHeap[index / 2] = temp;
                index = index / 2;
            }
        }
    }
 
    //힙의 데이터 delete. 루트의 데이터를 삭제한 후 반환하고, 루트에는 맨 마지막 위치의 데이터를 넣어준다.
    public int delete() {     
        if(isEmpty()) return;
        else {
            int root = minHeap[1];
            minHeap[1] = minHeap[idx];
            minHeap[idx--] = 0;
            minHeapify(); //다시 재정렬한다.
            return root;
        }
    }
 
//최소힙 정렬
    public void minHeapify() {
        int index = 1;
        int temp;    
 
        while(index * 2 <= idx) {
            if(minHeap[index * 2] < minHeap[index * 2 + 1] || minHeap[index * 2 + 1] == 0) { //왼쪽 자식의 값이 더 작은경우
                temp = minHeap[index];
                minHeap[index] = minHeap[index * 2];
                minHeap[index + 2] = temp;
                index = index * 2;    
            } else { //오른쪽 자식의 값이 더 작은경우
                temp = minHeap[index];
                minHeap[index] = minHeap[index * 2 + 1];
                minHeap[index + 2 + 1] = temp;
                index = index * 2 + 1;    
            }
        }
    }
}
 

reference