heapsort2 Heapsort Heap 구조((left) Complete binary tree)와 순서(부모 key값 >= 자식 key값)를 만족하는 binary tree HeapSort insert() -> upHeap() : 리프에서 루트까지 swap. O(logn) removeMax() -> deleteMax() : 끝값을 루트에 덮어씌운 뒤 리프까지 swap. findMax() : 루트노드의 키값 리턴. O(1) heapSort(E, n): 배열 E로부터 힙 H를 만든 뒤 max값을 빼서 E에 순서대로 넣는 과정을 n번 반복한다. deleteMax(H): 가장 마지막 노드 값을 가장 첫번째 값에 덮어씌움-> 마지막 노드 삭제-> fixHeap fixHeap(H, K): downHeap. 왼쪽 자식과 오른쪽 자식 중 더 큰 것과.. 2021. 4. 8. Sorting - Merge Sort / Heap Sort 1. Merge Sort 1) Merge 정렬되지 않은 A, B 두 배열이 주어졌을 때 하나의 정렬된 배열 C를 만든다. A, B 각각의 맨 앞 원소를 비교해 더 작은 값을 C로 옮기는 과정을 반복한다. W(n) = n-1 (맨 마지막 원소는 비교 없이 옮기기 때문) 2) Merge Sort 의사코드 void mergeSort(배열 E, int first, int last) if(first 2021. 4. 2. 이전 1 다음