자료구조, java) 힙(heap) 구현

힙(heap)

완전 이진트리로 만들어진 자료구조입니다.

 

최댓값 최솟값 찾기 위한 자료 구조형입니다.

제일 크거나 작은 노드가 루트에 있게 됩니다.

완전히 정렬이 되지는 않습니다.

 

최소 힙

조건 : 항상 부모 노드가 자식 노드보다 값이 작음

 

최대 힙

조건 : 항상 부모 노드가 자식 노드보다 값이 큼

---

 

삽입

 

트리의 마지막에 삽입합니다.

삽입 노드와 부모 노드의 힙 조건에 부합한 지 확인합니다.

만족하지 않다면 부모 노드와 swap

추가된 노드가 조건에 만족할 때까지 루트에 올라가거나 조건에 부합할 때까지 반복합니다.

시간 복잡도 :  O(log N)

 

삭제

 

루트 노드를 삭제합니다.

제일 마지막 노드를 루트로 이동합니다.

새로운 루트 노드가 힙 조건에 부합한 지 확인합니다.

만족하지 않으면 자식 노드와 swap

올라온 노드가 조건에 만족할 때까지 끝까지 내려가거나 조건에 부합할 때까지 반복합니다.

시간 복잡도 :  O(log N)

 

---

java 힙(heap) 구현, 최대 힙

출력문, 삽입, 삭제 기능만 구현해보겠습니다.

 

class를 생성하고 안에 ArrayList객체를 생성합니다.

만든 힙에 데이터를 넣을 때 해당 컬렉션에 들어가게 됩니다.

private ArrayList<Integer> heap;

 

클래스의 생성자 부분에는 heap을 초기화해줍니다.(더미 값을 하나 넣어줬습니다, 유의미한 자료는 인덱스 1부터 시작됩니다.)

heap = new ArrayList<>();
heap.add(Integer.MAX_VALUE);

출력문입니다. ArrayList size만큼 요소를 돌면서 출력해줍니다.

public void print() {
    for(int i = 1; i< heap.size(); i++) {
    	System.out.print(heap.get(i) + " ");
    }
}

 

삽 입문입니다.

val를 ArrayList에 넣어줍니다.

그 후 p에다가 ArrayList의 배열의 마지막 인덱스를 가져옵니다.

 

반복문을 돌립니다.

이 부분은 완전 이진트리 끝단에 들어간 것을 힙 조건에 맞게 스왑 하는 로직입니다.

 

p > 1(루트를 제외하고 최소 1개의 자식 노드가 있는지)

 heap.get(p / 2) < heap.get(p) (부모 노드 p /2, 자신을 비교)

조건에 부합하면 swap을 합니다.

 

부모 노드 값을 p의 위치에

자신의 값을 p/2위 치에

 

p/2가 부모 노드의 위치이고 p가 자신의 위치이므로

서로 교환된 것입니다.

 

그 후 p의 값을 p/2로 할당합니다. 이렇게 루트 노드까지 무한 반복됩니다.

public void insert(int val) {
    heap.add(val);
    int p = heap.size() -1;

    while(p > 1 && heap.get(p / 2) < heap.get(p)) {
        int temp = heap.get(p / 2);
        heap.set(p/2, heap.get(p));
        heap.set(p, temp);

        p = p/2;
    }

}

 

삭제 문입니다.

heap의 크기 -1 이

1보다 작을 시 (초기화할 때 더미 값을 넣었으므로 기본값은 1입니다.)

0을 반환합니다.

 

첫 번째 요소를 가지고 옵니다.

그 후 힙의 마지막 요소를 heap의 처음에 넣은 뒤

마지막 요소를 삭제합니다.

 

그 후 pos에 1을 할당합니다.(현재 위치입니다.)

 

Pos * 2가 힙 사이즈보다 작은지 확인합니다.

자식 노드가 있는지 확인하는 내용입니다.

 

max에는 자식 노드의 값, maxPos는 자식노드의 인덱스를 가집니다.

일단 왼쪽 자식노드의 정보를 가져온 후

if문으로 오른쪽 노드 조건을 확인한 뒤

통과되면 위에서 일단 가져온 왼쪽 자식 노드의 정보에 덮습니다.

 

그 후 부모 노드와 자식 노드 크기를 확인한 뒤

부모가 크면 "break"로 탈출합니다.

 

자식 노드가 더 값이 클 시

부모와 자식 노드를 swap한뒤

자식 노드의 위치 값을 저장한 뒤

 

또다시 반복문 처음으로 돌아옵니다.

public int delete() {
			
			if(heap.size() -1 < 1 ) {
				return 0; 
			}
			
			int deleteItem = heap.get(1);
			
			heap.set(1, heap.get(heap.size() -1));
			heap.remove(heap.size() -1);
			
			int pos =1;
			
			while((pos * 2) < heap.size()) {
				int max = heap.get(pos * 2);
				int maxPos = pos * 2;
				
				if(((pos * 2 + 1) < heap.size()) && 
						max < heap.get(pos * 2 + 1)) {
					max = heap.get(pos * 2 + 1);
					maxPos = pos * 2 + 1;
				}
				
				if(heap.get(pos) > max) {
					break;
				}
				
				int temp = heap.get(pos);
				heap.set(pos, heap.get(maxPos));
				heap.set(maxPos, temp);
				pos = maxPos;
			}
			return deleteItem;
		}