반응형
우선 순위 큐란
일반 큐와 다른 점은 데이터의 우선순위 존재하며 우선순위에 따라 출력
우선순위에서의 힙이란
우선 순위 큐를 구현하기 위한, 자유 저장소와 다른 힙이며 힙 순서 속성을 가진 완전 이진트리
가장 우선순위가 높은 데이터를 루트 노드를 가지는 완전 이진 트리
가장 마지막 노드를 찾기 위해서는 배열로 구현하는 방법을 선호
우선순위 힙에서의 삽입 후 '후처리'
1. 가장 마지막 위치에 새로운 노드를 추가
2. 부모 노드와 비교 후 우선순위가 높다면 변경
3. 루트 노드까지 비교하여 후처리
우선순위 힙에서의 제거 후 '후처리'
1. 가장 우선 순위가 높은 데이터 루트 데이터를 삭제
2. 가장 마지막 위치의 노드를 루트 노드로 이동
3. 왼쪽 자식과 아래쪽 자식을 우선 순위 비교하여 우선 순위가 높은 쪽과 위치 변경
4. 해당 노드의 위치를 찾을 때까지 반복하여 후처리
우선순위의 결정은 프로그래머의 선택
값이 작을수록 우선순위가 높은경우
값이 클수록 우선순위가 높은 경우
배열로 구현하는 우선 순위 힙
k번 인덱스 위치의 양쪽 자식 노드의 인덱스 구하는 방법
- 왼쪽 자식 노드 : 2k+1
- 오른쪽 자식 노드 : 2k+2
k번 인덱스 위치의 부모 노드의 인덱스 구하는 방법
- (k-1)/2의 몫
C 소스
Heap
Heap.h
/*
* Heap.h
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#ifndef PRIORITY_HEAP_H_
#define PRIORITY_HEAP_H_
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct tagHeapNode{
ElementType Data;
} HeapNode;
typedef struct tagNode{
HeapNode* Nodes;
int Capacity;
int UsedSize;
} Heap;
Heap* HEAP_Create(int initialSize);
void HEAP_Destroy(Heap* H);
void HEAP_Insert(Heap* H, ElementType NewData);
void HEAP_DeleteMin(Heap* H, HeapNode* Root);
int HEAP_GetParent(int Index);
int HEAP_GetLeftChild(int Index);
void HEAP_SwapNodes(Heap* H, int Index1, int Index2);
void HEAP_PrintNodes(Heap* H);
#endif /* 7_PRIORITY_HEAP_AND_QUEUE_HEAP_H_ */
Heap.c
/*
* Heap.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "PriorityHeap.h"
Heap* HEAP_Create(int InitialSize){
Heap* NewHeap = (Heap*)malloc(sizeof(Heap));
NewHeap->Capacity = InitialSize;
NewHeap->UsedSize = 0;
NewHeap->Nodes = (HeapNode*)malloc(sizeof(HeapNode)*NewHeap->Capacity);
printf("size : %d \n",sizeof(HeapNode));
return NewHeap;
}
void HEAP_Destroy(Heap* H){
free(H->Nodes);
free(H);
}
void HEAP_Insert(Heap* H, ElementType NewData){
int CurrentPosition = H->UsedSize;
int ParentPosition = HEAP_GetParent(CurrentPosition);
if(H->UsedSize == H->Capacity){
H->Capacity *=2;
H->Nodes = (HeapNode*) realloc(H->Nodes, sizeof(HeapNode) * H->Capacity);
}
H->Nodes[CurrentPosition].Data = NewData;
while(CurrentPosition > 0 && H->Nodes[CurrentPosition].Data < H->Nodes[ParentPosition].Data){
HEAP_SwapNodes(H, CurrentPosition, ParentPosition);
CurrentPosition = ParentPosition;
ParentPosition = HEAP_GetParent(CurrentPosition);
}
H->UsedSize++;
}
void HEAP_SwapNodes(Heap* H, int Index1, int Index2){
int CopySize = sizeof(HeapNode);
HeapNode* Temp = (HeapNode*)malloc(CopySize);
memcpy(Temp, &H->Nodes[Index1], CopySize);
memcpy(&H->Nodes[Index1], &H->Nodes[Index2], CopySize);
memcpy(&H->Nodes[Index2], Temp, CopySize);
free(Temp);
}
void HEAP_DeleteMin(Heap* H, HeapNode* Root){
int Parentposition = 0;
int LeftPosition = 0;
int RightPosition = 0;
memcpy(Root, &H->Nodes[0], sizeof(HeapNode));
memset(&H->Nodes[0], 0, sizeof(HeapNode));
H->UsedSize--;
HEAP_SwapNodes(H, 0, H->UsedSize);
LeftPosition = HEAP_GetLeftChild(0);
RightPosition = LeftPosition +1;
while(1){
int SelectedChild = 0;
if(LeftPosition >= H->UsedSize){
break;
}
if(RightPosition >= H->UsedSize){
SelectedChild = LeftPosition;
}else{
if(H->Nodes[LeftPosition].Data > H->Nodes[RightPosition].Data){
SelectedChild = RightPosition;
}else{
SelectedChild = LeftPosition;
}
}
if(H->Nodes[SelectedChild].Data < H->Nodes[Parentposition].Data){
HEAP_SwapNodes(H, Parentposition, SelectedChild);
Parentposition = SelectedChild;
}else{
break;
}
LeftPosition = HEAP_GetLeftChild(Parentposition);
RightPosition = LeftPosition + 1;
}
if(H->UsedSize < (H->Capacity /2)){
H->Capacity /=2;
H->Nodes = (HeapNode*) realloc(H->Nodes, sizeof(HeapNode) *H->Capacity);
}
}
int HEAP_GetParent(int Index){
return (int) ((Index -1 )/ 2);
}
int HEAP_GetLeftChild(int Index){
return (2*Index)+1;
}
void HEAP_PrintNodes(Heap* H){
int i = 0;
for(i = 0; i < H->UsedSize; i++){
printf("%d ", H->Nodes[i].Data);
}
printf("\n");
}
HeapMain.c
/*
* HeapMain.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "PriorityHeap.h"
int main(){
Heap* H = HEAP_Create(3);
HeapNode MinNode;
HEAP_Insert(H, 12);
HEAP_Insert(H, 87);
HEAP_Insert(H, 111);
HEAP_Insert(H, 34);
HEAP_Insert(H, 16);
HEAP_Insert(H, 75);
HEAP_PrintNodes(H);
HEAP_DeleteMin(H, &MinNode);
HEAP_PrintNodes(H);
HEAP_DeleteMin(H, &MinNode);
HEAP_PrintNodes(H);
HEAP_DeleteMin(H, &MinNode);
HEAP_PrintNodes(H);
HEAP_DeleteMin(H, &MinNode);
HEAP_PrintNodes(H);
HEAP_DeleteMin(H, &MinNode);
HEAP_PrintNodes(H);
HEAP_DeleteMin(H, &MinNode);
HEAP_PrintNodes(H);
return 0;
}
PriorityQueue
PriorityQueue.h
/*
* PriorityQueue.h
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#ifndef PRIORITYQUEUE_H_
#define PRIORITYQUEUE_H_
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef int PriorityType;
typedef struct tagePQNode{
PriorityType Priority;
void* Data;
} PQNode;
typedef struct tagPriorityQueue{
PQNode* Nodes;
int Capacity;
int UsedSize;
} PriorityQueue;
PriorityQueue* PQ_Create(int InitialSize);
void PQ_Destroy(PriorityQueue* PQ);
void PQ_Enqueue(PriorityQueue* PQ, PQNode NewNode);
void PQ_Dequeue(PriorityQueue* PQ, PQNode* Root);
int PQ_GetParent(int Index);
int PQ_GetLeftChild(int Index);
void PQ_SwapNodes(PriorityQueue* PQ, int Index1, int Index2);
int PQ_IsEmpty(PriorityQueue* PQ);
#endif /* 7_2_PRIORITY_QUEUE_PRIORITYQUEUE_H_ */
PriorityQueue.c
/*
* PriorityQueue.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "PriorityQueue.h"
PriorityQueue* PQ_Create(int InitialSize){
PriorityQueue* NewPQ = (PriorityQueue*)malloc(sizeof(PriorityQueue));
NewPQ->Capacity = InitialSize;
NewPQ->UsedSize = 0;
NewPQ->Nodes = (PQNode*)malloc(sizeof(PQNode)*NewPQ->Capacity);
return NewPQ;
}
void PQ_Destroy(PriorityQueue* PQ){
free(PQ->Nodes);
free(PQ);
}
void PQ_Enqueue(PriorityQueue* PQ, PQNode NewNode){
int CurrentPosition = PQ->UsedSize;
int ParentPosition = PQ_GetParent(CurrentPosition);
if(PQ->UsedSize == PQ->Capacity){
if(PQ->Capacity == 0){
PQ->Capacity =1;
}
PQ->Capacity *= 2;
PQ->Nodes = (PQNode*)realloc(PQ->Nodes, sizeof(PQNode)*PQ->Capacity);
}
PQ->Nodes[CurrentPosition] = NewNode;
while(CurrentPosition > 0 && PQ->Nodes[CurrentPosition].Priority < PQ->Nodes[ParentPosition].Priority){
PQ_SwapNodes(PQ, CurrentPosition, ParentPosition);
CurrentPosition = ParentPosition;
ParentPosition = PQ_GetParent(CurrentPosition);
}
PQ->UsedSize++;
}
void PQ_Dequeue(PriorityQueue* PQ, PQNode* Root){
int ParentPostion = 0;
int LeftPosition = 0;
int RightPosition = 0;
memcpy(Root, &PQ->Nodes[0], sizeof(PQNode));
memset(&PQ->Nodes[0], 0, sizeof(PQNode));
PQ->UsedSize--;
PQ_SwapNodes(PQ, 0, PQ->UsedSize);
LeftPosition = PQ_GetLeftChild(0);
RightPosition = LeftPosition + 1;
while(1){
int SelectedChild = 0;
if(LeftPosition >= PQ->UsedSize){
break;
}
if(RightPosition >= PQ->UsedSize){
SelectedChild = LeftPosition;
}else{
if(PQ->Nodes[LeftPosition].Priority > PQ->Nodes[RightPosition].Priority){
SelectedChild = RightPosition;
}else{
SelectedChild = LeftPosition;
}
}
if(PQ->Nodes[SelectedChild].Priority < PQ->Nodes[ParentPostion].Priority){
PQ_SwapNodes(PQ, ParentPostion, SelectedChild);
ParentPostion = SelectedChild;
}else{
break;
}
LeftPosition = PQ_GetLeftChild(ParentPostion);
RightPosition = LeftPosition + 1;
if( PQ->UsedSize < (PQ->Capacity /2)){
PQ->Capacity /= 2;
PQ->Nodes = (PQNode*)realloc(PQ->Nodes,sizeof(PQNode) * PQ->Capacity);
}
}
}
int PQ_GetParent(int Index){
return (int) ((Index-1)/2);
}
int PQ_GetLeftChild(int Index){
return (2 * Index) + 1;
}
void PQ_SwapNodes(PriorityQueue* PQ, int Index1, int Index2){
int CopySize = sizeof(PQNode);
PQNode* Temp = (PQNode*)malloc(CopySize);
memcpy(Temp, &PQ->Nodes[Index1], CopySize);
memcpy(&PQ->Nodes[Index1], &PQ->Nodes[Index2], CopySize);
memcpy(&PQ->Nodes[Index2], Temp, CopySize);
free(Temp);
}
int PQ_IsEmpty(PriorityQueue* PQ){
return (PQ->UsedSize == 0);
}
PriorityQueueMain.c
/*
* PriorityQueueMain.c
*
* Created on: 2019. 1. 7.
* Author: otrodevym
*/
#include "PriorityQueue.h"
void PrintNode(PQNode* Node){
printf("작업명 : %s (우선순위 : %d) \n", Node->Data, Node->Priority);
}
int main(){
PriorityQueue* PQ = PQ_Create(3);
PQNode Popped;
PQNode Nodes[7] = {
{34, (void*)"코딩"},
{12, (void*)"고객미팅"},
{87, (void*)"커피타기"},
{45, (void*)"문서작성"},
{35, (void*)"디버깅"},
{66, (void*)"이딱기"},
};
PQ_Enqueue(PQ, Nodes[0]);
PQ_Enqueue(PQ, Nodes[1]);
PQ_Enqueue(PQ, Nodes[2]);
PQ_Enqueue(PQ, Nodes[3]);
PQ_Enqueue(PQ, Nodes[4]);
PQ_Enqueue(PQ, Nodes[5]);
printf("큐에 남아 있는 작업의 수: %d \n", PQ->UsedSize );
while(!PQ_IsEmpty(PQ)){
PQ_Dequeue(PQ, &Popped);
PrintNode(&Popped);
}
return 0;
}
Java 소스
Heap
PriorityHeap.java
package g_priority_queue_and_heap;
import java.util.Arrays;
class HeapNode {
private int value;
public HeapNode() {
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
public class PriorityHeap {
HeapNode nodes[];
int capacity;
int usedSize;
public PriorityHeap() {
}
public PriorityHeap(int initialCapacity) {
this.capacity = initialCapacity;
this.usedSize = 0;
this.nodes = new HeapNode[this.capacity];
}
private PriorityHeap heapCreate(int initialSize) {
PriorityHeap newNode = new PriorityHeap(initialSize);
return newNode;
}
private void heapInsert(PriorityHeap heap, int newValue) {
int currentPosition = heap.usedSize;
int parentPosition = heapGetParent(currentPosition);
if (heap.usedSize == heap.capacity) {
heap.capacity *= 2;
HeapNode[] temp = new HeapNode[heap.capacity];
temp = Arrays.copyOf(heap.nodes, temp.length);
heap.nodes = temp;
}
HeapNode node = new HeapNode();
node.setValue(newValue);
heap.nodes[currentPosition] = node;
while (currentPosition > 0 &&
heap.nodes[currentPosition].getValue() < heap.nodes[parentPosition].getValue()) {
heapSwapNodes(heap, currentPosition, parentPosition);
currentPosition = parentPosition;
parentPosition = heapGetParent(currentPosition);
}
heap.usedSize++;
}
private int heapGetParent(int currentPosition) {
return (currentPosition-1)/2;
}
private int heapGetLeftChild(int currentPosition) {
return (2*currentPosition)+1;
}
private void heapSwapNodes(PriorityHeap heap, int currentPosition, int parentPosition) {
HeapNode temp = new HeapNode();
temp = heap.nodes[currentPosition];
heap.nodes[currentPosition] = heap.nodes[parentPosition];
heap.nodes[parentPosition] = temp;
}
private void heapDeleteMin(PriorityHeap heap, HeapNode Root) {
int parentPosition = 0;
int leftPosition = 0;
int rightPosition = 0;
heap.nodes[0].setValue(-1);
heap.usedSize--;
heapSwapNodes(heap, 0, heap.usedSize);
heap.nodes = Arrays.copyOf(heap.nodes, heap.nodes.length-1);
leftPosition = heapGetLeftChild(0);
rightPosition = leftPosition +1;
while(true) {
int selectedChild = 0;
if(leftPosition >= heap.usedSize) {
break;
}
if(rightPosition >= heap.usedSize) {
selectedChild = leftPosition;
}else {
if(heap.nodes[leftPosition].getValue() > heap.nodes[rightPosition].getValue()) {
selectedChild = rightPosition;
}else {
selectedChild = leftPosition;
}
}
if(heap.nodes[selectedChild].getValue() < heap.nodes[parentPosition].getValue()) {
heapSwapNodes(heap, parentPosition, selectedChild);
parentPosition = selectedChild;
}else {
break;
}
leftPosition = heapGetLeftChild(parentPosition);
rightPosition = leftPosition + 1;
}
}
private void heapPrintNodes(PriorityHeap heap) {
for(int i = 0; i < heap.usedSize; i++) {
System.out.print(" " + heap.nodes[i].getValue());
}
System.out.println();
}
public static void main(String args[]) {
PriorityHeap heap = new PriorityHeap();
heap = heap.heapCreate(3);
heap.heapInsert(heap, 12);
heap.heapInsert(heap, 87);
heap.heapInsert(heap, 111);
heap.heapInsert(heap, 34);
heap.heapInsert(heap, 16);
heap.heapInsert(heap, 75);
heap.heapPrintNodes(heap);
HeapNode node = new HeapNode();
heap.heapDeleteMin(heap, node);
heap.heapPrintNodes(heap);
heap.heapDeleteMin(heap, node);
heap.heapPrintNodes(heap);
heap.heapDeleteMin(heap, node);
heap.heapPrintNodes(heap);
heap.heapDeleteMin(heap, node);
heap.heapPrintNodes(heap);
heap.heapDeleteMin(heap, node);
heap.heapPrintNodes(heap);
}
}
PriorityQueue
PriorityQueue.java
package g_priority_queue_and_heap;
import java.util.Arrays;
import org.omg.CORBA.Current;
import d_tree.LeftChildRightSiblingTree;
class QueueNode {
private String value;
private int priority;
public QueueNode() {
}
public QueueNode(int priority, String value) {
super();
this.value = value;
this.priority = priority;
}
public QueueNode(String value) {
super();
this.value = value;
this.priority = 0;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
}
public class PriorityQueue {
QueueNode[] nodes;
int capacity;
int usedSize;
public PriorityQueue() {
}
private void pqCreate(int initialSize) {
this.capacity = initialSize;
this.usedSize = 0;
this.nodes = new QueueNode[this.capacity];
}
private void pqEnqueue(PriorityQueue pq, QueueNode newNode) {
int currentPosition = pq.usedSize;
int parentPosition = this.pqGetParent(currentPosition);
if(pq.usedSize == pq.capacity) {
if(pq.capacity == 0) {
pq.capacity = 1;
}
pq.capacity *= 2;
pq.nodes = Arrays.copyOf(pq.nodes, pq.capacity);
}
pq.nodes[currentPosition] = new QueueNode();
pq.nodes[currentPosition] = newNode;
while(currentPosition > 0 &&
pq.nodes[currentPosition].getPriority() < pq.nodes[parentPosition].getPriority()) {
this.pqSwapNodes(pq,currentPosition,parentPosition);
currentPosition = parentPosition;
parentPosition = this.pqGetParent(currentPosition);
}
pq.usedSize++;
}
private void pqSwapNodes(PriorityQueue pq, int currentPosition, int parentPosition) {
QueueNode temp = new QueueNode();
temp = pq.nodes[currentPosition];
pq.nodes[currentPosition] = pq.nodes[parentPosition];
pq.nodes[parentPosition] = temp;
}
private int pqGetParent(int currentPosition) {
return (currentPosition-1)/2;
}
private int pqGetLeftChild(int currentPosition) {
return (2*currentPosition)+1;
}
private QueueNode pqDequeue(PriorityQueue pq) {
int parentPosition = 0;
int leftPosition = 0;
int rightPosition = 0;
QueueNode popped = pq.nodes[0];
pq.usedSize--;
this.pqSwapNodes(pq, 0, pq.usedSize);
pq.nodes = Arrays.copyOf(pq.nodes, pq.nodes.length-1);
leftPosition = pqGetLeftChild(0);
rightPosition = leftPosition + 1;
while(true) {
int selectedChild = 0;
if(leftPosition >= pq.usedSize) {
break;
}
if(rightPosition >= pq.usedSize) {
selectedChild = leftPosition;
}else {
if(pq.nodes[leftPosition].getPriority() > pq.nodes[rightPosition].getPriority()) {
selectedChild = rightPosition;
}else {
selectedChild = leftPosition;
}
}
if(pq.nodes[selectedChild].getPriority() < pq.nodes[parentPosition].getPriority()) {
pq.pqSwapNodes(pq, parentPosition, selectedChild);
parentPosition = selectedChild;
}else {
break;
}
leftPosition = pqGetLeftChild(parentPosition);
rightPosition = leftPosition + 1;
}
return popped;
}
public int getUsedSize() {
return this.usedSize;
}
public static void main(String args[]) {
PriorityQueue pq= new PriorityQueue();
pq.pqCreate(3);
QueueNode nodes[] = new QueueNode[7];
nodes[0] = new QueueNode(34, "코딩");
nodes[1] = new QueueNode(12, "고객미팅");
nodes[2] = new QueueNode(87, "커피타기");
nodes[3] = new QueueNode(45, "문서작성");
nodes[4] = new QueueNode(35, "디버깅");
nodes[5] = new QueueNode(66, "이딱기");
pq.pqEnqueue(pq, nodes[0]);
pq.pqEnqueue(pq, nodes[1]);
pq.pqEnqueue(pq, nodes[2]);
pq.pqEnqueue(pq, nodes[3]);
pq.pqEnqueue(pq, nodes[4]);
pq.pqEnqueue(pq, nodes[5]);
System.out.println("큐에 남아 있는 작업의 수 : " + pq.getUsedSize());
QueueNode node = null;
while(!pq.isEmpty()) {
node = pq.pqDequeue(pq);
System.out.println(node.getValue());
}
}
private boolean isEmpty() {
return (this.usedSize == 0);
}
}
반응형
'개발(합니다) > 컴퓨터 일반&CS' 카테고리의 다른 글
| [알고리즘]그래프(인접리스트, 깊이우선탐색, 너비우선탐색) (0) | 2019.01.08 |
|---|---|
| [알고리즘]해시 테이블(Hash Table) (0) | 2019.01.08 |
| [알고리즘]탐색/검색(순차, 자기 구성, 이진 탐색, 레드블랙트리) (0) | 2019.01.05 |
| [알고리즘]정렬 알고리즘(버블, 삽입, 퀵) (0) | 2019.01.04 |
| [자료구조]트리(Tree) (0) | 2019.01.03 |
