[알고리즘] 힙 heap

[알고리즘] 힙 heap

heap이란?

힙이란 자료구조중 하나로, 트리구조에서 부모노드와 자식노드간에 대소관계를 성립 시켜서 문제활용에 이용합니다.

주로 최대값이나 최솟값을 이용하기 위해 사용하는 자료구조입니다.

또한 heap은 완전 이진트리여야 합니다.

완전 이진트리의 조건은

1.마지막 레벨을 제외하고 모든 노드가 가득 채워져 있어야 합니다.(자식 2개씩)

2.모든 노드들이 왼쪽부터 채워져야 합니다.

.

예제 코드

배열을 이용한 구현

import java.io.*; import java.util.*; public class Main { /* * */ static int max = 100; static int heap[] = new int[max]; static int heapsize = 0; public static void heapinit() { heapsize = 0; } public static int heapPush(int value) { if(heapsize + 1 > max) { System.out.println("full"); return 0; } heap[heapsize] = value; int current = heapsize; /* * 인덱스가 0으로 시작할때, * 부모인덱스는 = 자식의 인덱스 - 1 / 2 * 왼쪽 자식 인덱스 = 부모의인덱스 * 2 + 1 * 오른쪽 자식 인덱스 = 부모의 인덱스 * 2 + 2 * ************************************* * 인덱스가 1로 시작할때, * 부모인덱스 = 자식의 인덱스/2 * 왼쪽 자식 인덱스 = 부모의 인덱스 * 2 * 오른쪽 자식 인덱스 = 부모의 인덱스 * 2 +1 */ //부모의 우선순위가 자식의 우선순위 보다 더 높다면.... 교체 while(current > 0 && heap[current] < heap[(current-1) / 2]) { int temp = heap[(current-1) / 2]; heap[(current-1) / 2] = heap[current]; heap[current] = temp; current = (current -1) / 2; } //값이 push, 즉 추가 됬으므로 용량 1칸 증가. heapsize = heapsize + 1; return 1; } public static int heapPop() { //heapsize가 0보다 작거나 같다면 꺼낼게 없으므로 함수 바로 종료 if(heapsize <= 0) return -1; //힙의 꺼내기는 루트노드에서 시작 합니다. int value = heap[0]; //빼는 것이므로 사이즈하나 감소. heapsize = heapsize-1; //루트노드에 끝에값 넣기. heap[0] = heap[heapsize]; //0번 인덱스부터 확인 시작. int current = 0; //왼쪽 자식노드가 전체크기보다 작을떄까지 검사. while(current*2 +1 < heapsize) { int child; //오른쪽 자식노드가 전체크기와 같다면 자식변수에 왼쪽자식 노드 삽입. if(current*2 + 2 == heapsize) { child = current * 2 + 1; } //오른쪽 자식노드가 전체크기와 다르다면, 왼쪽자식노드와 오른쪽 자식 노드를 비교하여, 작은 자식을 자식변수에 넣어줍니다. else { child = heap[current*2 +1]

728x90

반응형

from http://kjs-dev.tistory.com/154 by ccl(A) rewrite - 2021-10-15 05:27:13