[알고리즘][정렬] 우선순위 큐와 힙

chellchell·2020년 9월 9일

힙 정렬

알고리즘 이론

목록 보기

11/11

우선순위 큐

정의

데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 됨
부여되는 우선순위에 따라 스택이나 큐로 동작 가능
배열, 연결리스트, 히프로 구현 가능
우선순위 큐의 종류
- 최소 우선순위 큐: 가장 우선순위가 낮은 요소를 먼저 삭제
- 최대 우선순위 큐: 가장 우선순위가 높은 요소를 먼저 삭제

추상자료형

힙

정의

우선순위 큐를 완전 이진 트리로 구현하는 방법
최솟값이나 최댓값을 쉽게 추출 가능
내부노드에 키를 저장하며 두 가지 속성를 만족하는 이진트리
- 힙순서 : key(v) ≥ key(parent(v))
- 완전 이진트리
히프의 종류
- 최소 히프(min heap): 부모 노드의 값 ≤ 자식노드의 값인 완전 이진 트리 (최소 히프의 루트 노드: 가장 작은 값을 가짐)
  - 정렬 시 최소 히프의 사용 권장
- 최대 히프(max heap): 부모 노드의 값 ≥ 자식노드의 값인 완전 이진 트리 (최대 히프의 루트 노드: 가장 큰 값을 가짐)
완전이진트리: 높이 h의 완전 트리에서 레벨 1~레벨 h-1까지는 포화 이진 트리이며 레벨 h에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진 트리(중간에 빈 노드가 없다)
1차원 배열로도 구현 가능
배열을 이용한 완전이진트리 구현 시 응용 식
- (왼쪽 자식의 인덱스)=(부모의 인덱스)*2
- (오른쪽 자식의 인덱스)=(부모의 인덱스)*2+1
- (부모의 인덱스)=(자식의 인덱스)/2
힙의 마지막 노드: 깊이 (h-1)의 가장 오른쪽 내부노드

추상자료형

구현1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FALSE 0

typedef struct HeapElementType {
	int key;
	char data;
}HeapNode;

typedef struct ArrayHeapType {
	int maxElementCount;//최대 노드 개수
	int currentElementCount;//현재 노드 개수
	HeapNode* pElement;//노드 저장을 위한 1차원 array
}ArrayMaxHeap, ArrayMinHeap;

ArrayMaxHeap* createArrayMaxHeap(int maxElementCount) {
	ArrayMaxHeap* pReturn = NULL;
	int i = 0;
	if (maxElementCount > 0) {
		pReturn = (ArrayMaxHeap*)malloc(sizeof(ArrayMaxHeap));
		if (pReturn != NULL) {
			pReturn->maxElementCount = maxElementCount;
			pReturn->currentElementCount = 0;
			pReturn->pElement = (HeapNode*)malloc(sizeof(HeapNode) * (maxElementCount + 1));
			if (pReturn->pElement == NULL) {
				printf("오류, 2번째 메모리 할당, createArrayList()\n");
				free(pReturn);
				return NULL;
			}
			memset(pReturn->pElement, 0, sizeof(HeapNode) * (maxElementCount + 1));
		}
		else {
			printf("오류, 메모리 할당, createArrayList()\n");
		}
	}
	else {
		printf("최대 원소 개수는 0보다 커야 합니다\n");
	}
	return pReturn;
}
void insertMaxHeapAH(ArrayMaxHeap* pHeap, HeapNode element) {
	int i = 0;
	if (pHeap != NULL) {
		if (pHeap->currentElementCount == pHeap->maxElementCount) {//히프의 크기를 초과하여 저장하는지 점검
			printf("오류, 히프가 가득찼습니다 [%d], insertMaxHeapAH()\n", pHeap->maxElementCount);
		}
		pHeap->currentElementCount++;//현재 노드 개수를 1증가
		i = pHeap->currentElementCount;//변수i는 현재 히프에서의 마지막 노드를 가르키는 위치 인덱스
		while ((i != 1) && (element.key > pHeap->pElement[i / 2].key)) {//부모 노드와 키 값 비교
			pHeap->pElement[i] = pHeap->pElement[i / 2];
			i /= 2;
		}
		pHeap->pElement[i] = element;
	}
}
HeapNode* deleteMaxHeapAH(ArrayMaxHeap* pHeap) {
	HeapNode* pReturn = NULL;
	HeapNode* pTemp = NULL;
	int i = 0;
	int parent = 0, child=0;
	if (pHeap != NULL && pHeap->currentElementCount > 0) {//현재 반환 가능한 노드가 있는지 점검
		pReturn = (HeapNode*)malloc(sizeof(HeapNode));
		if (pReturn == NULL) {//반환되는 노드에 대한 메모리 할당 및 점검
			printf("오류, 메모리 할당, deleteMaxHeapAH()\n");
			return NULL;
		}
		*pReturn = pHeap->pElement[1];//루트 노드가 반환되는 노드임. 반환되는 노드의 값으로 기존 루트 노드의 값을 대입
		i = pHeap->currentElementCount;//히프의 제일 마지막 위치 인덱스
		pTemp = &(pHeap->pElement[i]);//히프의 제일 마지막 노드를 가리킴
		pHeap->currentElementCount--;//현재 노드 개수 1개 감소

		parent = 1;//루프가 시작되는 곳은 루트 노드
		child = 2;//루트 노드의 왼쪽 자식 노드
		while (child <= pHeap->currentElementCount) {//히프의 제일 마지막 위치에 있는 노드를 만날 때까지
			if ((child < pHeap->currentElementCount)&&(pHeap->pElement[child].key<pHeap->[child+1].key)) {
				child++;//왼쪽 자식노드보다 오른쪽 자식노드의 키 값이 더 크다면, 오른쪽 자식 노드가 비교 대상이 되도록 위치 인덱스 child를 수정
			}
			if (pTemp->key >= pHeap->pElement[child].key) {
				break;//히프의 제일 마지막 노드와 현재 노드의 키 값을 비교하여 만약 마지막 노드의 키 값이 현재 노드보다 크거나 같다면 루프를 빠져 나온다. 이 위치에 삽입
			}
			pHeap->pElement[parent] = pHeap->pElement[child];//현재의 노드를 부모노드의 위치로 한 칸 이동
			parent = child;//아래 레벨로 이동
			child *= 2;
		}
		pHeap->pElement[parent] = *pTemp;
	}
	return pReturn;
}
void deleteArrayMaxHeap(ArrayMaxHeap* pHeap) {
	if (pHeap != NULL) {
		if (pHeap->pElement != NULL) {
			free(pHeap->pElement);
		}
		free(pHeap);
	}
}

구현2

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_ELEMENT 200
typedef struct {
	int key;
}element;
typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
}HeapType;
HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}
void init(HeapType* h) {
	h->heap_size = 0;
}
void insert_max_heap(HeapType* h, element item) {
	int i;
	i = ++(h->heap_size);
	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}
element delete_max_heap(HeapType* h) {
	int parent, child;
	element item, temp;
	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		//현재 노드의 자식노드 중 더 큰 자식노드 찾기
		if ((child < h->heap_size) && (h->heap[child].key < h->heap[child + 1].key))
			child++;
		if (temp.key >= h->heap[child].key)
			break;
		//한 단계 아래로 이동
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}
int main(void) {
	element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
	element e4, e5, e6;
	HeapType* heap;
	heap = create();
	init(heap);

	insert_max_heap(heap, e1);
	insert_max_heap(heap, e2);
	insert_max_heap(heap, e3);

	e4 = delete_max_heap(heap);
	printf("< %d >", e4.key);
	e5 = delete_max_heap(heap);
	printf("< %d >", e5.key);
	e6 = delete_max_heap(heap);
	printf("< %d >", e6.key);

	free(heap);
}

힙 정렬

히프 정렬: 정렬할 배열을 먼저 최소 히프로 변환 다음, 작은 원소부터 차례대로 추출하여 정렬하는 방법
1차원 배열로도 구현 가능

구현1


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma warning(disable:4996)
#define TRUE 1
#define FALSE 0

typedef struct HeapElementType {
	int key;
	char data;
}HeapNode;

typedef struct ArrayHeapType {
	int maxElementCount;//최대 노드 개수
	int currentElementCount;//현재 노드 개수
	HeapNode* pElement;//노드 저장을 위한 1차원 array
}ArrayMaxHeap, ArrayMinHeap;

ArrayMaxHeap* createArrayMaxHeap(int maxElementCount) {
	ArrayMaxHeap* pReturn = NULL;
	int i = 0;
	if (maxElementCount > 0) {
		pReturn = (ArrayMaxHeap*)malloc(sizeof(ArrayMaxHeap));
		if (pReturn != NULL) {
			pReturn->maxElementCount = maxElementCount;
			pReturn->currentElementCount = 0;
			pReturn->pElement = (HeapNode*)malloc(sizeof(HeapNode) * (maxElementCount + 1));
			if (pReturn->pElement == NULL) {
				printf("오류, 2번째 메모리 할당, createArrayList()\n");
				free(pReturn);
				return NULL;
			}
			memset(pReturn->pElement, 0, sizeof(HeapNode) * (maxElementCount + 1));
		}
		else {
			printf("오류, 메모리 할당, createArrayList()\n");
		}
	}
	else {
		printf("최대 원소 개수는 0보다 커야 합니다\n");
	}
	return pReturn;
}
void insertMinHeapAH(ArrayMinHeap* pHeap, HeapNode element) {
	int i = 0;
	if (pHeap != NULL) {
		if (pHeap->currentElementCount == pHeap->maxElementCount) {//히프의 크기를 초과하여 저장하는지 점검
			printf("오류, 히프가 가득찼습니다 [%d], insertMaxHeapAH()\n", pHeap->maxElementCount);
		}
		pHeap->currentElementCount++;//현재 노드 개수를 1증가
		i = pHeap->currentElementCount;//변수i는 현재 히프에서의 마지막 노드를 가르키는 위치 인덱스
		while ((i != 1) && (element.key < pHeap->pElement[i / 2].key)) {//부모 노드와 키 값 비교
			pHeap->pElement[i] = pHeap->pElement[i / 2];
			i /= 2;
		}
		pHeap->pElement[i] = element;
	}
}
HeapNode* deleteMinHeapAH(ArrayMaxHeap* pHeap) {
	HeapNode* pReturn = NULL;
	HeapNode* pTemp = NULL;
	int i = 0;
	int parent = 0, child = 0;
	if (pHeap != NULL && pHeap->currentElementCount > 0) {//현재 반환 가능한 노드가 있는지 점검
		pReturn = (HeapNode*)malloc(sizeof(HeapNode));
		if (pReturn == NULL) {//반환되는 노드에 대한 메모리 할당 및 점검
			printf("오류, 메모리 할당, deleteMaxHeapAH()\n");
			return NULL;
		}
		*pReturn = pHeap->pElement[1];//루트 노드가 반환되는 노드임. 반환되는 노드의 값으로 기존 루트 노드의 값을 대입
		i = pHeap->currentElementCount;//히프의 제일 마지막 위치 인덱스
		pTemp = &(pHeap->pElement[i]);//히프의 제일 마지막 노드를 가리킴
		pHeap->currentElementCount--;//현재 노드 개수 1개 감소

		parent = 1;//루프가 시작되는 곳은 루트 노드
		child = 2;//루트 노드의 왼쪽 자식 노드
		while (child <= pHeap->currentElementCount) {//히프의 제일 마지막 위치에 있는 노드를 만날 때까지
			if ((child < pHeap->currentElementCount) && (pHeap->pElement[child].key > pHeap->[child + 1].key)) {
				child++;//왼쪽 자식노드보다 오른쪽 자식노드의 키 값이 더 크다면, 오른쪽 자식 노드가 비교 대상이 되도록 위치 인덱스 child를 수정
			}
			if (pTemp->key < pHeap->pElement[child].key) {
				break;//히프의 제일 마지막 노드와 현재 노드의 키 값을 비교하여 만약 마지막 노드의 키 값이 현재 노드보다 크거나 같다면 루프를 빠져 나온다. 이 위치에 삽입
			}
			pHeap->pElement[parent] = pHeap->pElement[child];//현재의 노드를 부모노드의 위치로 한 칸 이동
			parent = child;//아래 레벨로 이동
			child *= 2;
		}
		pHeap->pElement[parent] = *pTemp;
	}
	return pReturn;
}
void deleteArrayMinHeap(ArrayMaxHeap* pHeap) {
	if (pHeap != NULL) {
		if (pHeap->pElement != NULL) {
			free(pHeap->pElement);
		}
		free(pHeap);
	}
}
void heapSort(int value[], int count) {
	int i = 0;
	ArrayMinHeap* pHeap = NULL;
	pHeap = createArrayMinHeap(8);
	if (pHeap != NULL) {
		for (i = 0; i < count; i++) {
			HeapNode node;
			node.key = value[i];
			insertMinHeapAH(pHeap, node);
		}
		for (i = 0; i < count; i++) {
			HeapNode* pNode = deleteMinHeapAH(pHeap);
			if (pNode != NULL) {
				value[i] = pNode->key;
				free(pNode);
			}
		}
		deleteArrayMinHeap(pHeap);
	}
}

구현2

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)
#define MAX_ELEMENT 200
#define SIZE 8

typedef struct {
	int key;
}element;
typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
}HeapType;
HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}
void init(HeapType* h) {
	h->heap_size = 0;
}
void insert_max_heap(HeapType* h, element item) {
	int i;
	i = ++(h->heap_size);
	while ((i != 1) && (item.key > h->heap[i / 2].key)) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}
element delete_max_heap(HeapType* h) {
	int parent, child;
	element item, temp;
	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		//현재 노드의 자식노드 중 더 큰 자식노드 찾기
		if ((child < h->heap_size) && (h->heap[child].key < h->heap[child + 1].key))
			child++;
		if (temp.key >= h->heap[child].key)
			break;
		//한 단계 아래로 이동
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}
void heap_sort(element a[], int n) {
	int i;
	HeapType* h;
	h = create();
	init(h);
	for (i = 0; i < n; i++) {
		insert_max_heap(h, a[i]);
	}
	for (i = (n - 1); i >= 0; i--) {
		a[i] = delete_max_heap(h);
	}
	free(h);
}
int main(void) {
	element list[SIZE] = { 23,56,11,9,56,99,27,34 };
	heap_sort(list, SIZE);
	for (int i = 0; i < SIZE; i++) {
		printf("%d ", list[i].key);
	}
	printf("\n");
}

특징

최선, 평균, 최악: $O(nlogn)$
히프 자료구조를 이용하여 히프에 삽입, 삭제만을 통해 정렬
히프 생성에 필요한 추가 메모리 필요
안정성 유지되지 않음

chellchell

high hopes

이전 포스트

[알고리즘][정렬] 우선순위 큐와 힙

알고리즘 이론

우선순위 큐

정의

추상자료형

힙

정의

추상자료형

구현1

구현2

힙 정렬

구현1

구현2

특징

[알고리즘][그래프의 탐색] 그래프의 깊이 우선 탐색 Part 1

0개의 댓글