Introduction to Algorithms (14) 썸네일형 리스트형 [Introduction to Algorithms] 힙 특성 유지하기 1) 최대 힙 특성 유지하기 - 최대 힙 특성을 유지하기 위해 MAX-HEAPIFY가 호출된다. 입력은 배열 A와 배열의 인덱스 i다. MAX-HEAPIFY를 호출할 때 LEFT(i)와 RIGHT(i)를 루트로 하는 이진 트리가 최대 힙이라고 가정하는데, A[i]가 자식들보다 작아 최대 힙 특성에 어긋나는 일이 생길 수 있다. MAX-HEAPIFY 프로시저는 최대 힙에서 A[i] 값을 "내려보냄"으로써, 인덱스 i를 루트로 하는 서브 트리가 최대 힙이 되도록 한다. MAX-HEAPIFY(A, i)l = LEFT(i)r = RIGHT(i)if l A[i] largest = lelse largest = iif r A[largest] largest = rif largest != i .. [Introduction to Algorithms] 힙 정렬 알고리즘 1) 개요- 힙 정렬 알고리즘은 BUILD-MAX-HEAP으로 입력 배열 A[1...n](n = A.length]를 최대 힙으로 만들면서 시작한다. 최대 원소가 루트 A[1]에 저장되어 있으므로 이것을 A[n]과 교환하면 정확히 마지막 자리에 넣을 수 있다. 이제 힙에서 (A.heap-size를 줄여서) 노드 n을 "제거"하면 A[1..(n-1)]을 최대 힙으로 만드는 것은 그리 어렵지 않다. - 루트의 자식들은 최대 힙으로 남아 있지만, 새로운 루트는 최대 힙 특성을 어길 수 있다. 따라서 최대 힙 특성을 다시 지키도록 MAX-HEAPIFY(A,1)을 호출한다. 힙 정렬 알고리즘은 이 과정을 힙 크기가 n-1일때부터 2로 줄어들때까지 반복한다. HEAPSORT(A)1 BUILD-MAX-HEA.. [Introduction to Algorithms] 퀵 정렬 1) 개요- 퀵 정렬은 원소 수가 n개인 입력 배열을 최악의 경우 O(n2)에 정렬하는 알고리즘이다. 퀵 정렬은 최악의 경우에는 수행시간이 느리지만, 평균 수행시간이 O(nlgn)으로 매우 효율적이고, O(nlgn) 표현에 숨겨진 상수 인자도 매우 작다. 또한 내부 정렬이라는 장점도 있고, 가상 메모리 환경에서도 잘 동작해 일반적으로 실제 문제에서 가장 유용한 정렬 방법이다. - 이 글에서는 퀵 정렬 알고리즘과 분할할 때 사용하는 중요한 서브 루틴을 설명한다. 퀵 정렬은 복잡한 알고리즘이기 때문에 성능에 관해 직관적인 논의롤 시작하고, 정확한 분석은 이 글의 끝으로 미룬다. - 그 다음은 무작위 추출을 이용하는 랜덤화된 퀵 정렬을 소개한다. 이 알고리즘은 평균 수행시간이 적게 들고 모든 .. [Introduction to Algorithms] 위상정렬 1) 개요 - 깊이 우선 검색을 이용해 방향 비순환 그래프("dag")의 위상 정렬을 수행하는 것이 가능합니다. 하나의 dag인 G=(V,E)의 위상 정렬은 G가 간선 (u,v)를 가질 때, u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열 하는 것이다. (그래프가 순환을 가진다면 그러한 선형 나열은 불가능하다) - 그래프의 위상 정렬은 모든 방향 간선이 왼쪽에서 오른쪽으로 향할 수 있도록 수평선을 따르는 정점의 나열이라고 볼 수 있다. 그러므로 위상 정렬은 통상적인 "정렬"과는 다르다. - 여러 응용 분야에서 사건들 사이의 우선순위를 나타내기 위해 방향 비순환 그래프를 사용한다. 그림 22.7은 Bumstead 교수가 아침에 옷을 입을 때, 발생하는 하나의 예를 보.. 이전 1 2 다음
