반응형
개념
트리 중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진 트리인 힙(Heap)을 만들기 위한 정렬 방법
I. 힙 정렬 (Heap Sort)의 개요
가. 힙 정렬의 정의
- 트리 중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진 트리인 힙(Heap)을 만들기 위한 정렬 방법
나. 힙 정렬의 특징
- 힙 구조에서 가장 큰 값의 위치는 루트에 있음.
- 배열에 저장하는 것이 효율적임.
- 수행시간 복잡도: O(n·log2n)
Ⅱ. 힙 정렬의 삽입∙삭제 과정 및 사례
가. 힙 정렬의 삽입과정 및 사례
|
||||||
![]() |
⇒ | ![]() |
⇒ | ![]() |
⇒ | ![]() |
void insert_max_heap(element item, int *n) { int i; if(HEAP_FULL(*n)) { fprintf(stderr,”The heap is full. ₩n”); exit(1); } i = ++(*n); while((i!=1)&&(item.key>heap[i/2].key)) { heap[i] = heap[i/2]; i /= 2; } heap[i] = item; } |
반응형
나. 힙 정렬의 삭제과정 및 사례
|
||||||
![]() |
⇒ | ![]() |
⇒ | ![]() |
⇒ | ![]() |
element delete_max_heap(int *n) { element item, temp; if(HEAP_EMPTY(*n)) { fprintf(stderr,”The heap is empty₩n”); exit(1); } item = heap[1]; temp = heap[(*n)--]; parent = 1; child = 2; while(child <= *n) { if((child < *n) && (heap[child].key < heap[child+1].key)) child++; if(temp.key>=heap[child].key) break; heap[parent] = heap[child]; parent = child; child *= 2; } heap[parent] = temp; return item; } |
[Algorithm] 문자열 탐색 알고리즘 - 원시적 탐색, 카프라빈 탐색, KMP탐색, 보이어 무어 탐색
[Algorithm] 문자열 탐색
개 념문자열 탐색 (원시적 탐색, 카프라빈 탐색, KMP탐색, 보이어 무어 탐색) 문자열 데이터 안에서 특정 패턴의 검색 대상이 되는 문자열을 탐색하는 알고리즘 I. 문자열 탐색의 개요 가.
infoofit.tistory.com
[용어/개념] AAA(Authentication Authorization Accounting) 프로토콜
[용어/개념] AAA(Authentication Authorization Accounting) 프로토콜
Ⅰ. DIAMETER AAA의 이해 가. AAA(Authentication Authorization Accounting) 프로토콜의 정의- 불법적인 네트워크 서비스 사용을 방지하고자 사용자 인증, 권한제어, 과금을 위해 다양한 네트워크 기술과 플랫폼
infoofit.tistory.com
반응형