반응형 heap 정렬1 heap 정렬 u 히프(heap)를 이용해 정렬 ･ 히프 : 우선순위 큐의 일종 Ø 정렬할 원소를 모두 공백 히프에 하나씩 삽입 Ø 한 원소씩 삭제 →제일 큰 원소가 삭제됨 Ø 이 원소를 리스트의 뒤에서부터 차례로 삽입 Ø 오름차순으로 정렬된 리스트를 생성 HeapSort(a[]) n ← a.length - 1; // n은 히프 크기(원소의 수) // a[0]은 사용하지 않고 a[1 : n]의 원소를 오름차순으로 정렬 for (i ← n/2; i ≥ 1; i ← i-1) do // 배열 a[]를 히프로 변환 heapify(a, i, n); // i는 내부 노드 for (i ← n-1; i ≥ 1; i ← i-1) do { // 배열 a[]를 오름차순으로 정렬 temp ← a[1]; // a[1]은 제일 큰 원소 a[1.. 2007. 3. 13. 이전 1 다음 반응형
