160106P(수)

자료구조 Chpter13 힙

 

우선순위 큐(priority queue)

들어온 순서가 아닌 우선순위가 더 높은 자료를 먼저 처리

 

힙(heap)

우선순위 큐와 비슷한 의미

우선순위 큐가 개념적인 자료구조로 단지 우선순위가 높은 자료를 먼저 처리한다는 것을 의미한다면 힙은 좀 더 구체적인 자료구조를 의미한다.

 

우선순위를 정하는 방법과 우선순위가 높은 자료를 뽑아내는 방법 등의 구체적인 방법을 포함한다.

 

기본형태

큐에 들어있는 자료 중에서 우선순위가 가장 높은것을 골라내는 것이다.

큐의 가장 앞부분에 우선순위가 가장 높은 자료를 위치시키면 굳이 모든 자료를 다 정렬할 필요가 없다.

 

큐는 가장 앞부분(front)부분을 제외하고는 정렬되어 있지 않으며, 우선순위가 가장 높은 자료가 제거되고나면 그다음 우선순위가 front에 위치하게 된다. 이로 인해 생긴 공백은 메꿔지게 되며 힘 기법에 따라 다르다.

 

기본 메소드

삽입(insert) + 삭제(delete)

 

1. 자료를 입력할 때마다 큐 내부에서 우선순위가 가장 높은 자료를 큐의 가장 앞으로 보낸다.

삽입 시 O(N)

삭제 시 O(1)

 

∴ 삽일할 때 보다 삭제를 수행할 때 적은 시간이 걸려야 하는 자료구조에 적합

 

2. 자료 삽입시에는 큐의 마지막 부분에 자료를 그냥 추가하고 삭제할 때 우선순위가 가장 높은 자료를 찾아서 뽑아낸다.

삽입 시 O(1)

삭제 시 O(N)

 

∴ 삭제 시 빠른 반응이 필요하지 않은 경우

 

이진 힙(binary heap)

완전 이진 트리(complete binary tree)를 이용해서 그 트리의 루트에 우선순위가 가장 높은 자료를 입력시키는 방법

 

이진 힙이 되기위한 조건

1. 트리의 구조는 완전 이진트리여야 한다.

2. 부모 노드는 자신의 두 자식노드보다 우선순위가 높아야 한다.

 

트리는 개념적인 자료구조이므로 메모리에 저장하려면 구체적 방법 필요

완전 이진트리는 빈공간이 없으므로 배열이 적합하다.

 

레벨 순서 순회(level order traverse) 알고리즘

완전 이진트리로 표현된 힙을 실제 배열에 표현하는 방법

레벨이 동일한 노드드들을 순서대로 읽는다.

 

 

삽입

1. 삽입할 자료를 트리의 마지막 위치에 넣는다.

2. 부모노드와 우선순위를 비교하여 계속 반복한다.

1. 부모노드의 우선순위가 더 높은경우, 삽입을 끝낸다.

2. 부모노드의 우선순위가 더 낮은경우, 부모노드와 교환

3. 트리의 루트가 되면 삽입을 끝낸다.

 

약한정렬(weakly order)

힙은 우선순위가 가장 큰 자료가 루트에 위치해 있다는 것을 보장해줄 뿐 그 외의 자료들은 입력 순서에 따라서 위치하는 곳이 다르다.

 

삭제

루트 노드를 삭제할 때 빈공간을 채우기 위한 기법

 

1. 루트 노드를 삭제한다.

2. 힙의 마지막 노드를 루트노드의 자리로 옮긴다.

3. 자식 노드들과 우선순위를 비교한다.

1. 두 자식노드의 우선순위가 더 낮을 경우 삭제를 끝낸다.

2. 우선순위가 더 높은 자식노드가 있을 경우 두 자식노드 중 우선순위가 더 높은 노드와 교환한 뒤 다시 비교한다.

3. 자식을 갖지 않는 leaf노드가 될 경우 삭제를 끝낸다.

 

BinaryHeep.java

pulbic class Node {

private int value;

 

public void setValue(int val) {

value = val;

}

 

public int getValue() {

return value;

}

}

 

public class BinaryHeap {

// 힙이 현재 가지고있는 노드의 개수

private int curSize;

 

private Node[] bHeap;

 

public BinaryHeap(int arraySize) {

bHeap = new Node[arraySize];

curSize = 0;

}

 

public int getParent(int child) {

if((child % 2) == 1) {

return (int)((child - 1) / 2);

}

 

else

return (int)((child - 2) / 2);

}

 

public int getLeftChild(int parent) {

return (parent * 2) + 1;

}

 

public int getRightChild(int parent) {

return (parent  * 2) + 2;

}

 

public int insert(int data) {

Node node;

Node tmp;

 

// 삽입하려는 노드의 배열에서의 현재 위치

int point;

 

int parent;

 

node = new Node();

node.setValue(data);

 

point = curSize;

bHeap[point] = node;

curSize++;

 

for(int i = 0; i < curSize; i++) {

if(point == 0) {

return 0;

}

 

parent = getParent(point);

if(bHeap[parent].getValue() < bHeap[point].getValue()) {

return 0;

}

 

else {

tmp = bHeap[point];

bHeap[point] = bHeap[parent];

bHeap[parent] = tmp;

 

point = parent;

}

}

return -1;

}

 

public Node delete() {

Node delNode;

Node tmp;

int point;

int left, right;

int winner;

 

tmp = new Node();

 

// delNode = bHeap[0].getValue == -1

// -1대신 null이 쓰여야 하지만 getValue의 return 타입이 int이다.

// 내생각에는 null이 맞다고 생각한다.

if((delNode = bHeap[0].getValue == null) {

return delNode;

}

 

point = 0;

bHeap[poiint] = bHeap[curSize - 1];

curSize--;

 

for(int i = 0; i < curSize; i++) {

left = getLeftChild(point);

right = getRightChild(point);

 

if(bHeap[left].getValue() > bHeap[right].getValue()) {

winner = right;

}

else {

winner = left;

}

 

if(bHeap[winner].getValue() > bHeap[point].getValue()) {

rerutn delNode;

}

else {

tmp = bHeap[point];

bHeap[point] = bHeap[winner];

bHeap[winner] = tmp;

 

point = winner;

}

}

return delNode;

}

 

public void showHeap() {

for(int i = 0; i < curSize; i++) {

System.out.print(bHeap[i].getValue() + " ");

}

System.out.println("");

}

}

 

힙 정렬(Heap sort)

삭제 메소드 수행 시 우선순위가 가장 큰 자료가 뽑힌다는 힙의 기본 성질을 이용한 정렬

delete 연산으로 나온 노드들을 별도의 배열에 순서대로 저장하면 정돈된 배열을 얻을 수 있다.

 

장점

구현이 간단하다.

 

단점

별도 배열을 위한 메모리가 필요

힙 구성에 O(N)의 시간이 걸리고 삭제 메소드를 N번 시행해야 한다.

다른 정렬에 비해서 비교적 느린 속도이다.

 

이러한 단점을 극복하기 위해서 별도의 배열이 아니라 삭제되면서 생긴 힙메모리의 빈공간에 기록하는 방법을 쓴다.

 

HeapSort.java

pulbic class Node {

private int value;

 

public void setValue(int val) {

value = val;

}

 

public int getValue() {

return value;

}

}

 

public class BinaryHeap {

// 힙이 현재 가지고있는 노드의 개수

private int curSize;

 

private Node[] bHeap;

 

public BinaryHeap(int arraySize) {

bHeap = new Node[arraySize];

curSize = 0;

}

 

public int getParent(int child) {

if((child % 2) == 1) {

return (int)((child - 1) / 2);

}

 

else

return (int)((child - 2) / 2);

}

 

public int getLeftChild(int parent) {

return (parent * 2) + 1;

}

 

public int getRightChild(int parent) {

return (parent  * 2) + 2;

}

 

public int insert(int data) {

Node node;

Node tmp;

 

// 삽입하려는 노드의 배열에서의 현재 위치

int point;

 

int parent;

 

node = new Node();

node.setValue(data);

 

point = curSize;

bHeap[point] = node;

curSize++;

 

for(int i = 0; i < curSize; i++) {

if(point == 0) {

return 0;

}

 

parent = getParent(point);

if(bHeap[parent].getValue() < bHeap[point].getValue()) {

return 0;

}

 

else {

tmp = bHeap[point];

bHeap[point] = bHeap[parent];

bHeap[parent] = tmp;

 

point = parent;

}

}

return -1;

}

 

public Node delete() {

Node delNode;

Node tmp;

int point;

int left, right;

int winner;

 

tmp = new Node();

 

// delNode = bHeap[0].getValue == -1

// -1대신 null이 쓰여야 하지만 getValue의 return 타입이 int이다.

// 내생각에는 null이 맞다고 생각한다.

if((delNode = bHeap[0].getValue == null) {

return delNode;

}

 

point = 0;

bHeap[poiint] = bHeap[curSize - 1];

curSize--;

 

for(int i = 0; i < curSize; i++) {

left = getLeftChild(point);

right = getRightChild(point);

 

if(left > curSize) {

bHeap[curSize] = delNode;

 

return delNode;

}

else if(right > curSize) {

winner = left;

}

else {

if(bHeap[left].getValue() > bHeap[right].getValue()) {

winner = right;

}

else {

winner = left;

}

 }

 

if(bHeap[winner].getValue() > bHeap[point].getValue()) {

bHeap[curSize] = delNode;

 

rerutn delNode;

}

else {

tmp = bHeap[point];

bHeap[point] = bHeap[winner];

bHeap[winner] = tmp;

 

point = winner;

}

}

bHeap[curSize] = delNode;

 

return delNode;

}

 

public void showHeap() {

for(int i = 0; i < curSize; i++) {

System.out.print(bHeap[i].getValue() + " ");

}

System.out.println("");

}

 

public void showHeapSort() {

for(int i = 0; i < curSize; i++) {

System.out.print(bHeap[i].getValue() + " ");

}

System.out.print("|");

 

for(int i = curSize; i < arraySize; i++) {

System.out.print(bHeap[i].getValue() + " ");

}

System.out.println("");

}

}

 

더 효율적인 프로그래밍

위에서 배운 힙 삽입 알고리즘은 교환 1번에 3번의 연산이 필요하다.

1. 삽입

2. 삽입 노드를 임시노드(tmp)에 복사

3. 부모 노드를 자식노드에 복사

4. 임시노드를 부모노드에 복사

 

해결

버블 삽입 - 2번의 연산

자료 삽입시 빈공간을 만든뒤 그 빈공간이 원하는 자리에 위치될 때까지 부모노드의 값을 그 빈공간에 복사

1. 빈공간 삽입

2. 부모노드를 자식노드에 복사

3. 빈공간에 값 삽입