힙소트

Heapsort
힙소트
Sorting heapsort anim.gif
무작위로 치환된 값의 배열을 정렬하는 힙소트 실행입니다.알고리즘의 첫 번째 단계에서는 배열 요소가 힙 속성을 충족하도록 정렬됩니다.실제 정렬이 이루어지기 전에 히프 트리 구조가 간략하게 표시되어 있습니다.
학급정렬 알고리즘
data 구조어레이
최악의 경우 성능
베스트 케이스 성능( logn) { O ( \ n) （ display O ( n \ log n ) } (구분키)
O ( )\ O ( ) (동일한 키)
평균 성능
최악의 경우 공간의 복잡성( ){ O ( ) }O ( (1보조

컴퓨터 과학에서 힙소트는 비교 기반 정렬 알고리즘입니다.힙소트는 개선된 선택 정렬로 생각할 수 있습니다.선택 정렬과 마찬가지로 힙소트는 입력을 정렬된 영역과 정렬되지 않은 영역으로 나누고, 여기서 가장 큰 요소를 추출하여 정렬되지 않은 영역을 반복적으로 축소합니다.선택 정렬과 달리 힙소트는 정렬되지 않은 영역의 선형 시간 스캔으로 시간을 낭비하지 않습니다. 대신 힙소트는 정렬되지 않은 영역을 힙 데이터 구조에서 유지하여 각 [1]단계에서 가장 큰 요소를 더 빨리 찾습니다.

대부분의 머신에서는 퀵소트보다 실행 속도가 다소 느리지만 최악의 경우 O(n log n) 실행 시 보다 유리하다는 장점이 있습니다.힙소트는 임플레이스 알고리즘이지만 안정적인 정렬은 아닙니다.

힙소트는 1964년 [2]J. W. J. 윌리엄스에 의해 발명되었다.이것은 또한 Williams가 이미 [3]유용한 데이터 구조로서 제시한 힙의 탄생이기도 하다.같은 해, 로버트 W. Floyd는 어레이를 즉석에서 정렬할 수 있는 개선된 버전을 발표하여 트리소트 [3]알고리즘에 대한 초기 연구를 계속했습니다.

개요

힙소트 알고리즘은 두 부분으로 나눌 수 있습니다.

첫 번째 단계에서는 데이터로부터 힙을 구축합니다(이진 힙 » 힙 구축 참조).힙은 종종 완전한 이진 트리의 레이아웃과 함께 배열에 배치됩니다.완전한 바이너리 트리는 바이너리 트리 구조를 어레이 인덱스에 매핑합니다.각 어레이 인덱스는 노드를 나타냅니다.노드의 부모, 왼쪽 자식 브랜치 또는 오른쪽 자식 브랜치의 인덱스는 단순한 표현식입니다.제로 베이스 어레이의 경우 루트 노드는 인덱스0 에 저장됩니다.i현재 노드의 인덱스입니다.

iParent(i) = 바닥 함수가 실수를 가장 큰 선행 정수로 매핑하는 바닥(i-1) / 2)입니다. iLeftChild(i) = 2*i + 1 iRightChild(i) = 2*i + 2

두 번째 단계에서는 히프에서 가장 큰 요소(히프의 루트)를 제거하고 어레이에 삽입하는 것을 반복하여 정렬된 어레이를 작성한다.힙 속성은 삭제될 때마다 업데이트됩니다.모든 개체가 힙에서 제거되면 정렬된 배열이 됩니다.

힙소트는 현장에서 수행할 수 있습니다.배열은 정렬된 배열과 힙의 두 부분으로 나눌 수 있습니다.여기에서는, 어레이로서의 힙의 스토리지를 그림으로 나타내고 있습니다.힙의 불변성은 각 추출 후에도 유지되므로 유일한 비용은 추출 비용입니다.

알고리즘.

힙소트 알고리즘에서는 먼저 목록을 최대 힙으로 변환하여 목록을 준비해야 합니다.그런 다음 알고리즘은 목록의 첫 번째 값을 마지막 값과 반복적으로 스왑하여 힙 동작에서 고려되는 값의 범위를 1개 줄이고 새로운 첫 번째 값을 힙 내의 해당 위치에 넣습니다.이는 고려된 값의 범위가 하나의 값이 될 때까지 반복됩니다.

순서는 다음과 같습니다.

  1. 문의처buildMaxHeap()기능하고 있습니다.다른 이름으로도 불린다.heapify()O( ) \ O ( )operations 에서 힙을 만듭니다.
  2. 목록의 첫 번째 요소를 마지막 요소와 연결합니다.목록의 고려 범위를 1개 줄입니다.
  3. 문의처siftDown()목록에서 기능을 수행하여 힙 내의 적절한 인덱스에 새 첫 번째 요소를 체로 걸러냅니다.
  4. 목록의 고려 범위가 하나의 요소가 아닌 경우 스텝 (2)로 이동합니다.

그buildMaxHeap()동작은 한 번 실행되며 퍼포먼스는 O(n)입니다.그siftDown()함수는 O(log n)이며 n회 호출됩니다.따라서 이 알고리즘의 성능은 O(n + n log n) = O(n log n)입니다.

유사 코드

다음으로 알고리즘을 의사 코드로 실장하는 간단한 방법을 나타냅니다.어레이는 제로 베이스로swap는 배열의 두 요소를 교환하는 데 사용됩니다.'아래로' 이동은 뿌리에서 잎으로, 또는 낮은 지수에서 높은 지수로 이동하는 것을 의미합니다.정렬 중에 가장 큰 요소는 다음 위치에 있는 힙의 루트에 있습니다.a[0]이 종류의 마지막에는 가장 큰 요소가 있습니다.a[end].

procedure hipsort(a, count) 입력: 길이 카운트의 순서 없는 배열 a(가장 큰 값이 루트에 오도록 배열 a에 힙을 구축함) 힙ify(a, count) (다음 루프는 [0:end]가 힙이고 모든 요소가 그 이전의 모든 요소보다 크다는 불변성을 유지합니다(따라서 [end:count]는 순서대로 정렬됨). ←count - 1 when end > 0 do ( a [ 0 ]는 루트와 최대값) 스왑은 정렬된 요소 앞으로 이동합니다.) swap(a[end], a[0])(히프 크기를 1개 줄임) ← end - 1(스왑으로 인해 힙 속성이 손상되었으므로 복원) siffDown(a, 0, end)

정렬 루틴에서는 두 개의 서브루틴을 사용합니다.heapify그리고.siftDown전자는 일반적인 임플레이스 힙 구축 루틴이며 후자는 구현을 위한 일반적인 서브루틴입니다.heapify.

('a'의 요소를 힙 순서대로 배치, in-place) 프로시저 heapify(a, count)는 (시작이 마지막 상위 노드의 'a'에 있는 인덱스를 할당받음) (0 기반 배열의 마지막 요소는 인덱스 카운트-1에 있습니다. 해당 요소의 부모를 찾으십시오) 시작 중 ← iParent(카운트-1)가 시작되는 동안 ('에 있는 노드를 'count-1)가 올바르게 시작됨)입니다.시작 인덱스 아래의 모든 노드가 힙 순서입니다.) sifterDown(a, start, count - 1) (다음 상위 노드로 이동) start ← start - 1 (루트를 아래로 이동한 후 모든 노드/노드는 힙 순서입니다) (자녀에 루트가 있는 힙이 유효한 것으로 가정하여 인덱스 '시작'인 힙을 복구합니다.)TDown(, 시작, 끝)가← 시작 만약 a[스왑]<>는 동안 iLeftChild(뿌리)≤ 끝(반면 뿌리 아이를 적어도 한명 있)아이 ← iLeftChild(뿌리)(뿌리의 레프트 아이)스왑← 뿌리(아이의 트랙으로 바꾸고 싶어 지키);a[아이] 다음 교환 ← 아이(이 있다면 올바른 어린이와 아이. 는 greater) child+1 and end 및 a[sign] < a[child+1]이면 swap = child+1이면 swap ← root이면 swap + 1이 됩니다(루트는 가장 큰 요소를 보유합니다. 하위 항목에 루트된 힙이 유효하다고 가정하므로, 이는 작업이 완료되었음을 의미합니다.) 그렇지 않으면 swap(a[root], a[root]) root ← swap(지금 하위 항목 체인을 계속하지 않음)을 반환합니다.

그heapify절차는 힙 속성을 확립하기 위해 아래쪽으로 연속적으로 이동함으로써 힙을 아래에서 위로 구축하는 것으로 간주할 수 있습니다.히프를 하향식으로 구축하고 위로 이동하는 대체 버전(아래 그림 참조)은 이해하기 쉬울 수 있습니다.이것.siftUpversion은 빈 힙에서 시작하여 연속적으로 요소를 삽입하는 것으로 시각화할 수 있습니다.siftDown위의 버전에서는 입력 배열 전체가 완전하지만 "파손된" 힙으로 처리되며 마지막 비패키지 서브노드(즉 마지막 부모 노드)부터 "파손된"됩니다.

"siftDown" 버전과 "siftUp" 버전 간의 시간 복잡도 차이.

또,siftDownheapify 버전은 O(n) 시간 복잡도를 가지지만,siftUp아래 버전에서는 각 요소를 한 [4]번에 하나씩 빈 힙에 삽입하는 것과 동등하기 때문에 O(n log n) 시간의 복잡성이 있습니다.이는 일견 직관에 반하는 것처럼 보일 수 있는데, 이는 전자가 후자의 로그 시간 체계의 함수의 절반만 호출하는 것이 명백하기 때문이다. 즉, 이들은 점근 분석에 영향을 미치지 않는 상수 인자에 의해서만 달라 보이기 때문이다.

이 복잡도 차이의 이면에 있는 직관을 파악하려면 1회 중 발생할 수 있는 스왑 횟수에 유의하십시오.siftUp콜이 발신되는 노드의 깊이에 따라 콜이 증가합니다.중요한 점은 힙에 있는 "shallow" 노드보다 더 많은 "deep" 노드가 있기 때문에 siffUp은 힙의 "하단" 노드 또는 그 부근에 있는 노드에서 실행되는 거의 선형적인 콜 수에 대해 완전한 로그 실행 시간을 가질 수 있다는 것입니다.한편, 콜이 발신되는 노드의 깊이가 커질수록, 1개의 siffDown 콜중에 발생하는 스왑의 수는 감소합니다.그 때문에, 다음의 경우에,siftDown heapify를 호출하고 있습니다.siftDown최하위 및 가장 많은 노드 스위칭에서는 각 체인지 콜은 체인지 콜이 이루어지는 노드의 높이(히프 하단에서)와 같은 수의 스왑이 발생합니다.즉, 콜의 절반가량이siftDown에는 최대 1개의 스왑이 있고 콜의 약 4분의 1은 최대 2개의 스왑이 있습니다.

힙소트 알고리즘 자체에는 어느 버전의 힙파이를 사용하는 O(n log n) 시간의 복잡성이 있습니다. 

루트)의 절차 heapify(a,count)은(말(왼쪽의 인덱스에 할당됩니다) 아이:=1는 동안 끝<>카운트 siftUp(는, 0, 끝)끝( 적절한 장소가는 지수 끝에서 끝으로 검지 위에 모든 노드 히프 주문에 있는 노드를 체로 치다):= 끝+1(후에 살피는 것이 다. 아니요.de all node is in heap order) procedure sifterUp(a, start, end)이 입력됩니다.start는 시프팅할 힙의 상한치를 나타냅니다.end는 체업할 노드입니다. child : = end while child > start parent : = iParent ( child ) iParent ( child > a [ parent ]< child ]< child > start parent : > a max-parent order ( a [ parent ], a [ child ]) 스왑 ( child ） child : ） child : = parent : （ child ） sifeatternow （ class

주의해 주세요.siftDown각 스왑 후 콜이 필요한 접근 방식은siftDownsubroutine을 사용하여 파손된 힙을 수정합니다.siftUp서브루틴만으로는 파손된 힙을 수정할 수 없습니다.스왑 후 매번 히프를 구축하려면heapify"siftUp"은 "siftDown"이 아닌 "siftUp"은 스왑되는 요소가 최종 위치에 있는 것으로 가정하기 때문에 불변성이 충족될 때까지 힙 내의 하위 항목을 지속적으로 조정할 수 있습니다.사용하기 위한 조정된 의사 코드siftUp접근법은 다음과 같습니다. 

procedure hipsort(a, count) 입력: 길이 카운트의 순서 없는 배열 a(가장 큰 값이 루트에 오도록 배열 a에 힙을 구축한다) 힙ify(a, count) (다음 루프는 [0:end]가 힙이고 모든 요소가 그 이전의 모든 요소보다 크다는 불변성을 유지합니다(따라서 [end:count]는 순서대로 정렬됩니다).← count - 1 while end > 0 do(a[0]는 루트이고 가장 큰 값입니다. 스왑은 정렬된 요소 앞으로 이동합니다.) swap(a[end], a[0])(스왑이 힙 속성을 폐기한 후 siffUp을 사용하여 힙을 확장함) heapify(a, end) ← end - 1

바리에이션

플로이드의 힙 구조

모든 실제 구현에 포함된 기본 알고리즘의 가장 중요한 변형은 O(n) 시간에 실행되며 시프업이 아닌 시프다운을 사용하는 Floyd의 힙 구성 알고리즘입니다. 따라서 시프업을 구현할 필요가 전혀 없습니다.

플로이드의 알고리즘은 사소한 힙에서 시작하여 반복적인 리프 추가가 아니라 리프부터 시작하여 리프 자체로는 사소하지만 유효한 힙임을 관찰한 후 부모를 추가합니다.요소 n/2부터 시작하여 역방향으로 작업하는 각 내부 노드는 체중을 내려 유효한 힙의 루트가 됩니다.마지막 단계는 첫 번째 요소를 선별하고 그 후 전체 배열이 힙 속성에 따릅니다.

히프소트의 Floyd의 힙 구축 단계에서의 최악의 비교 수는 2n2 - 2s(n2) - e(n)와 같은 것으로 알려져 있습니다2.여기서 s(n)는 2진수 표현에서의 1비트 수이고2 e(n)는 후행0비트 수입니다.[5]

Floyd의 힙 구성 알고리즘의 표준 구현은 데이터 크기가 CPU [6]: 87 캐시의 크기를 초과하면 대량의 캐시 누락이 발생합니다.대규모 데이터 세트의 퍼포먼스는 위의 [7][8]레벨로 진행되기 전에 모든 서브히프를 한 레벨로 결합하는 것이 아니라 가능한 한 빨리 서브히프를 결합하는 것으로 훨씬 향상할 수 있습니다.

보텀업 힙소트

보텀업 힙소트는 중요한 요소에 필요한 비교 횟수를 줄이는 변종입니다.일반 힙소트는 최악의 경우 평균 [9]2n2 로그 n + O(n) 비교가 필요하지만, 상향식 변형에서는 평균 [9]n 로그2 n + O(1) 비교가 필요하며, 최악의 [10]경우 1.5n 로그2 n + O(n) 비교가 필요합니다.

비교가 저렴한 경우(예: 정수 키)는 하향식 힙소트가 메모리에서 이미 로드된 값을 비교하기 때문에 차이는 [11]중요하지 않습니다.단, 비교에 함수 호출 또는 기타 복잡한 로직이 필요한 경우에는 상향식 힙소트가 유리합니다.

이것은, 다음의 기능을 개선함으로써 실현됩니다.siftDown절차.이 변경으로 선형 시간 힙 구축 단계가 [12]다소 개선되었지만 두 번째 단계에서는 더 중요합니다.일반적인 힙소트와 마찬가지로 두 번째 단계의 각 반복은 힙의 맨 위 a[0]를 추출하여 남는 간격을 a[end]로 채우고 이 후자 요소를 힙 아래로 이동시킵니다.그러나 이 요소는 힙의 가장 낮은 레벨에서 추출됩니다.즉, 힙에서 가장 작은 요소 중 하나이기 때문에 아래로 [13]이동하려면 많은 단계를 거쳐야 합니다.일반적인 힙소트에서는 체다운의 각 단계에서 최소 3개의 요소(새로운 노드와 그 2개의 자식)를 찾기 위해 2개의 비교가 필요합니다.

대신 상향 힙소트는 레벨당 하나의 비교만 사용하여 트리의 리프 레벨(-)를 삽입하는 것처럼)에 대한 가장 큰 자녀의 경로를 찾습니다.다른 말로 하자면, 그것은 자신과 모든 조상이 형제자매보다 크거나 같은 특성을 가진 잎을 발견한다.(같은 키가 없는 경우 이 리프에는 고유합니다).그런 다음 이 리프에서 위쪽(레벨당 1회 비교 사용)에서 경로의 올바른 위치를 검색하여 a[end]를 삽입합니다.이 위치는 일반 힙소트가 찾은 위치와 동일하며 삽입을 수행하기 위해 같은 수의 교환이 필요하지만 해당 [10]위치를 찾기 위해 필요한 비교는 더 적습니다.

바닥까지 내려갔다가 다시 올라오기 때문에 몇몇 [14]작가들에 의해 튕겨지면서 힙소트라고 불린다. 

← 나는 만약 a[iRightChild(j)]을(는 j의 두 아이들의 큰 경우를 결정한다)는 동안 iRightChild(j)≤ 끝니 기능 leafSearch(는, 나는, 끝)다;a[iLeftChild(j)] 다음 j ← iRightChild(j) 다른← iLeftChild(j)( 지난 수준에서 있을 것이 단지 하나의 아이)j 만약 iLeftChild(j)≤ 끝난 다음 j ← iL j.도롱뇽의 일종아이(j)는 j를 반환한다.

의 반환값leafSearch변경된 에 사용됩니다.siftDown루틴:[10] 

프로시저 siffDown(a, i, end)은 j ← leafSearch(a, i, i, end)이며, a[i] do j ← i[j] a[j] ← a[i]인 반면 j > i는 x, a[iParent(j) j ← iParent(j)를 스왑합니다.

Bottom-up humpsort는 크기가 16000 [9]미만인 어레이에서 중앙 3개의 피벗 선택으로 Quicksort를 능가하는 것으로 발표되었습니다.

이 알고리즘의 2008년 재평가에서는 정수키에 대한 일반적인 힙소트보다 빠르지 않은 것으로 나타났다.이는 아마도 현대의 분기 예측이 상향식 힙소트가 회피할 [11]수 있는 예측 가능한 비교 비용을 무효화하기 때문일 것이다.

한층 더 세분화하면, 선택한 리프까지의 패스로 바이너리 검색이 실행되어 (n+1)(log22(n+1) + log2(n+1) + O(logn2) 비교의 최악의 경우에 정렬되어, n2 logn - 1.4427n [15]비교의 정보 이론 하한에 가까워집니다.

내부 노드당 2개의 추가 비트(n-element 힙의 경우 총 n-1비트)를 사용하여 어느 쪽이 큰지에 대한 정보를 캐시하는 바리안트(왼쪽, 오른쪽 및 알 [12]수 없음의 3가지 경우를 저장하기 위해 2비트가 필요함)는 n logn2 + 1.1n보다 적은 값을 사용합니다.[16]

기타 변종류

  • Ternary 힙소트는 이진 힙 대신 3진 힙을 사용합니다.즉, 힙의 각 요소에는 3개의 하위 요소가 있습니다.프로그래밍이 더 복잡하지만 스왑 및 비교 작업이 항상 몇 배 줄어듭니다.이는 3진 힙의 각 시프다운스텝에 3개의 비교와 1개의 스왑이 필요한 반면 바이너리 힙에서는 2개의 비교와 1개의 스왑이 필요하기 때문입니다.3진 힙의 두 레벨은 3 = 9개의 요소를 포함하며2, 2 = [citation needed]8만을 포함하는3 이진 힙의 세 레벨과 동일한 수의 비교로 더 많은 작업을 수행합니다.이것은 주로 학문적 또는 학생의 [17]연습으로서 흥미롭다. 왜냐하면 추가적인 복잡성은 사소한 비용 절감의 가치가 없고, 상향식 무더기는 두 가지 모두를 능가하기 때문이다.
  • 메모리에 최적화된[6]: 87 힙소트는 하위 항목 수를 더 늘림으로써 힙소트의 참조 인접성을 향상시킵니다.이렇게 하면 비교 횟수가 증가하지만 모든 하위 항목이 메모리에 연속적으로 저장되기 때문에 힙 트래버설 중에 액세스하는 캐시 행 수가 줄어들어 순 성능이 향상됩니다.
  • Out-of-Place[18][19][13] 힙소트는 최악의 경우를 배제하고 n logn2 + O(n) 비교를 보장함으로써 보텀업 힙소트를 개선합니다.최대값이 지정되면 빈 공간을 정렬되지 않은 데이터 값으로 채우지 말고 -"sentinel 값으로 채웁니다.이 값은 백업을 "바운스"하지 않습니다.이것은, 임플레이스(및 비재귀) 「QuickHeapsort」[20]알고리즘의 프리미티브로서 사용할 수 있는 것이 판명되었습니다.먼저 빠른 정렬과 같은 파티션 패스를 수행하지만 배열에서 분할된 데이터의 순서를 반대로 합니다.(범용성을 잃지 않고) 작은 파티션이 피벗보다 큰 파티션이라고 가정합니다.피벗 파티션은 어레이의 끝에 위치해야 하지만 역 파티셔닝 단계에서는 처음에 위치시킵니다.작은 파티션에서 힙을 형성하고 그 파티션에서 out-of-place 힙소트를 실행하여 추출된 최대값을 배열 끝의 값과 교환합니다.이것들은 피벗보다 작습니다.즉, 힙 내의 값보다 작기 때문에 -sentinel 값으로 기능합니다.힙소트가 완료되면(및 피벗이 배열의 정렬된 끝 바로 이전으로 이동), 파티션의 순서가 반대로 되어 어레이의 선두에 있는 큰 파티션도 같은 방법으로 정렬됩니다(비테일 재귀가 없기 때문에 퀵소트의 O(log n) 스택 사용도 배제됩니다).
  • 스무스소트[21] 알고리즘은 1981년 Edsger W. Dijkstra에 의해 개발된 힙소트의 변형이다.힙소트와 마찬가지로 스무드소트의 상한은 O(n log n)입니다.스무스소트의 장점은 입력이 이미 어느 정도 정렬되어 있는 경우 O(n) 시간에 가까워진다는 것입니다.한편 힙소트는 초기 정렬 상태에 관계없이 O(n log n)의 평균을 냅니다.그 복잡성 때문에 스무스소트는 [citation needed]거의 사용되지 않는다.
  • Levcopoulos와 Peterson은[22] 데카르트 나무 더미에 기초한 힙포트의 변형을 묘사한다.우선, O(n) 시간의 입력으로부터 데카르트 트리를 구축해, 그 루트를 1 요소 바이너리 힙에 배치한다.그런 다음 바이너리 힙에서 최소값을 반복적으로 추출하여 트리의 루트 요소를 출력하고 왼쪽 및 오른쪽 자식(있는 경우)을 데카르트 [23]트리에 추가합니다.그들이 나타내듯이 입력이 이미 거의 정렬되어 있는 경우, 데카르트 트리는 매우 불균형하고, 왼쪽과 오른쪽의 노드가 거의 없기 때문에 바이너리 힙은 작게 유지되며, 알고리즘은 이미 거의 정렬되어 있는 입력에 대해 O(n log n)보다 더 빠르게 정렬할 수 있습니다.
  • weak humpsort 등의 여러 변형에서는 최악의 경우 노드당 1비트의 추가 상태를 사용하여 n개의2 로그 n+O(1) 비교가 필요합니다.이 추가 비트는 알고리즘을 실제로 배치하지는 않지만, 요소 내에서 이 알고리즘을 위한 공간을 찾을 수 있다면 이러한 알고리즘은 단순하고 효율적이지만 [7]: 40 키 비교가 충분히 저렴하고 상수 계수가 중요하지 [24]않은 경우(예: 정수 키)에는 이진 힙보다 여전히 느립니다.
  • Katajainen의 "최종 힙소트"에는 추가 스토리지가 필요하지 않으며 n개의2 로그 n+O(1) 비교 및 동일한 수의 요소 [25]이동을 수행합니다.그러나 비교 비용이 매우 많이 들지 않는 한 이는 훨씬 더 복잡하며 정당화되지 않습니다.

다른 종류와의 비교

힙소트는 주로 매우 효율적인 또 다른 범용 일괄 비교 기반 정렬 알고리즘인 QuickSort와 경쟁합니다.

Humpsort의 주요 장점은 단순하고 비재귀적인 코드, 최소한의 보조 스토리지 요구 사항 및 신뢰할 수 있는 우수한 성능입니다. 즉, Humpsort의 가장 좋은 경우와 최악의 경우 서로 간에 작은 상수 계수 내이며 비교 정렬에 대한 이론적 하한선 내에 있습니다.사전 정렬된 입력에 대해 O(n log n)보다 더 나은 결과를 얻을 수는 없지만, QuickSort의 O(n2) 최악의 경우에도 문제가 없습니다(후자는 신중한 구현으로 피할 수 있지만, 이는 QuickSort를 훨씬 더 복잡하게 만들며, 가장 인기 있는 솔루션 중 하나인 Introsort는 목적을 위해 힙소트를 사용합니다).

이 트리의 주요 단점은 참조의 낮은 인접성과 본질적으로 직렬 특성입니다. 암묵 트리에 대한 액세스는 광범위하게 분산되어 있으며 대부분 랜덤이며 병렬 알고리즘으로 변환할 수 있는 간단한 방법이 없습니다.

이를 통해 임베디드 시스템, 실시간 컴퓨팅 및 Linux [27]커널과 같이 악의적으로 선택된 [26]입력과 관련된 시스템에서 널리 사용됩니다.또한 정렬에 병목 현상이 발생할 것으로 예상되지 않는 애플리케이션에도 적합합니다.

잘 구현된 퀵소트는 보통 [6][28]힙소트보다 2~3배 빠릅니다.QuickSort는 비교가 적은 편이지만 이는 사소한 요인입니다.(2배의 비교를 주장하는 결과는 하향식 버전을 측정하는 것입니다. § 상향식 힙소트를 참조하십시오.)QuickSort의 주요 장점은 훨씬 더 나은 참조 지역입니다. 파티셔닝은 공간적 지역성이 좋은 선형 스캔이며, 재귀적 하위 분할은 시간적 지역성이 좋습니다.추가 작업을 통해 대부분 브랜치가 필요 없는 코드로 QuickSort를 구현할 수 있으며 여러 CPU를 사용하여 하위 파티션을 병렬로 정렬할 수 있습니다.따라서 성능 향상으로 구현 작업이 정당화될 경우 빠른 정렬이 선호됩니다.

다른 주요 O(n log n) 정렬 알고리즘은 병합 정렬이지만 힙소트와 직접 경합하는 경우는 거의 없습니다.δ(n)의 추가 공간(입력 크기의 거의 절반)에 대한 병합 정렬의 요구사항은 병합 정렬이 명확한 이점을 가지고 있는 경우를 제외하고 일반적으로 금지됩니다.

  • 안정된 정렬이 필요한 경우
  • (부분적으로) 사전 정렬된 입력을 이용하는 경우
  • 연결 목록 정렬(이 경우 병합 정렬에는 최소 여유 공간이 필요함)
  • 병렬 정렬: 머지 정렬은 퀵 정렬보다 더 잘 병렬화되어 선형에 가까운 속도 향상을 쉽게 달성할 수 있습니다.
  • 외부 정렬. 병합 정렬은 참조 인접성이 우수합니다.

예

가장 작은 것부터 가장 큰 것까지 정렬하는 목록을 {6, 5, 3, 1, 8, 7, 2, 4 }로 합니다.(주의: '히프 구축' 단계: 큰 노드는 작은 노드 상위 노드보다 낮게 유지되지 않습니다.부모와의 교환 후 다른 교환이 필요한지 재귀적으로 확인합니다.이것에 의해, 히프 바이너리 트리의 작은 수치보다 큰 수치를 유지할 수 있습니다).

힙소트의 예.

히프를 구축하다

히프 새로 추가된 요소 요소 스왑
NULL 6
6 5
6, 5 3
6, 5, 3 1
6, 5, 3, 1 8
6, 5, 3, 1, 8 5, 8
6, 8, 3, 1, 5 6, 8
8, 6, 3, 1, 5 7
8, 6, 3, 1, 5, 7 3, 7
8, 6, 7, 1, 5, 3 2
8, 6, 7, 1, 5, 3, 2 4
8, 6, 7, 1, 5, 3, 2, 4 1, 4
8, 6, 7, 4, 5, 3, 2, 1

정렬

히프 요소 스왑 요소 삭제 정렬된 배열 세부 사항
8, 6, 7, 4, 5, 3, 2, 1 8, 1 힙에서 8을 삭제하려면 8과 1을 스왑합니다.
1, 6, 7, 4, 5, 3, 2, 8 8 힙에서 8을 삭제하고 정렬된 어레이에 추가
1, 6, 7, 4, 5, 3, 2 1, 7 8 힙 내 순서가 아니므로 1과 7을 스왑합니다.
7, 6, 1, 4, 5, 3, 2 1, 3 8 힙 내 순서가 아니므로 1과 3을 스왑합니다.
7, 6, 3, 4, 5, 1, 2 7, 2 8 7과 2를 스왑하여 힙에서 7을 삭제합니다.
2, 6, 3, 4, 5, 1, 7 7 8 힙에서 7을 삭제하고 정렬된 어레이에 추가
2, 6, 3, 4, 5, 1 2, 6 7, 8 2와 6은 힙 내에서 순서가 다르므로 스왑합니다.
6, 2, 3, 4, 5, 1 2, 5 7, 8 힙 내 순서가 아니므로 2와 5를 스왑합니다.
6, 5, 3, 4, 2, 1 6, 1 7, 8 힙에서 6을 삭제하려면 6과 1을 스왑합니다.
1, 5, 3, 4, 2, 6 6 7, 8 힙에서 6을 삭제하고 정렬된 어레이에 추가
1, 5, 3, 4, 2 1, 5 6, 7, 8 힙 내 순서가 아니므로 1과 5를 스왑합니다.
5, 1, 3, 4, 2 1, 4 6, 7, 8 힙 내 순서가 아니므로 1과 4를 스왑합니다.
5, 4, 3, 1, 2 5, 2 6, 7, 8 힙에서 5를 삭제하려면 5와 2를 스왑합니다.
2, 4, 3, 1, 5 5 6, 7, 8 힙에서 5를 삭제하고 정렬된 어레이에 추가
2, 4, 3, 1 2, 4 5, 6, 7, 8 힙 내 순서가 아니므로 2와 4를 스왑합니다.
4, 2, 3, 1 4, 1 5, 6, 7, 8 4와 1을 스왑하여 힙에서 4를 삭제합니다.
1, 2, 3, 4 4 5, 6, 7, 8 힙에서 4를 삭제하고 정렬된 어레이에 추가
1, 2, 3 1, 3 4, 5, 6, 7, 8 힙 내 순서가 아니므로 1과 3을 스왑합니다.
3, 2, 1 3, 1 4, 5, 6, 7, 8 3과 1을 스왑하여 힙에서 3을 삭제합니다.
1, 2, 3 3 4, 5, 6, 7, 8 힙에서 3을 삭제하고 정렬된 어레이에 추가
1, 2 1, 2 3, 4, 5, 6, 7, 8 힙 내 순서가 아니므로 1과 2를 스왑합니다.
2, 1 2, 1 3, 4, 5, 6, 7, 8 힙에서 2를 삭제하려면 2와 1을 스왑합니다.
1, 2 2 3, 4, 5, 6, 7, 8 힙에서 2를 삭제하고 정렬된 어레이에 추가
1 1 2, 3, 4, 5, 6, 7, 8 힙에서 1을 삭제하고 정렬된 어레이에 추가합니다.
1, 2, 3, 4, 5, 6, 7, 8 완료된

메모들

  1. ^ Skiena, Steven (2008). "Searching and Sorting". The Algorithm Design Manual. Springer. p. 109. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8. [H]eapsort is nothing but an implementation of selection sort using the right data structure.
  2. ^ 윌리엄스 1964
  3. ^ a b Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. p. 209. ISBN 978-0-521-88037-4.
  4. ^ "Priority Queues". Archived from the original on 9 September 2020. Retrieved 10 September 2020.
  5. ^ Suchenek, Marek A. (2012). "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program". Fundamenta Informaticae. 120 (1): 75–92. doi:10.3233/FI-2012-751.
  6. ^ a b c LaMarca, Anthony; Ladner, Richard E. (April 1999). "The Influence of Caches on the Performance of Sorting". Journal of Algorithms. 31 (1): 66–104. CiteSeerX 10.1.1.456.3616. doi:10.1006/jagm.1998.0985. S2CID 206567217. 특히 98페이지의 그림 9c를 참조하십시오.
  7. ^ a b Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). "Performance Engineering Case Study: Heap Construction" (PostScript). ACM Journal of Experimental Algorithmics. 5 (15): 15–es. CiteSeerX 10.1.1.35.3248. doi:10.1145/351827.384257. S2CID 30995934. 대체 PDF 소스.
  8. ^ 첸 Jingsen, Edelkamp, 스테판, Elmasry, 암르;Katajainen, Jyrki(27–31 2012년 8월)."In-place다 건설 최적화 비교는, 끝내고 캐시 Misses"(PDF).컴퓨터 과학 2012년의 수학적 기초 컴퓨터 과학의 수학 기초에 37위 국제 회의.강의 노트 컴퓨터 과학으로.Vol7464.브라티슬라바, 슬로바키아.를 대신하여 서명함. 259–270. doi:10.1007/978-3-642-32589-2_25.아이 에스비엔 978-3-642-32588-5.S2CID 1462216.원본(PDF)에서 12월 29일 2016년에 Archived.참고 특히 그림 3.
  9. ^ a b c 베게너는 인고(13일 9월 1993년)."BOTTOM-UP HEAPSORT, HEAPSORT 구타 장면을 새로운 변형, 평균하여, QUICKSORT(만약 n은 작은)"(PDF).이론적 컴퓨터 과학이다. 118(1):81–98. doi:10.1016(93)90364-y.작동하는지부터 1990년(수리 기초 컴퓨터 과학 회의에서)에 게재한 비록 이것이 재판, 기술은 칼손이 1987년에 출판되었다.[15]
  10. ^ a b c 플라이셔, 루돌프(1994년 2월)."재정 긴축을 낮춰 Bottom-Up-Heapsort의 최악의 경우행"(PDF).Algorithmica.11(2):104–115. doi:10.1007/bf01182770. hdl:11858/00-001M-0000-0014-7B02-C.S2CID 21075180.또한 플라이셔, 루돌프(4월 1991년) 있다.재정 긴축을 낮춰 Bottom-Up-Heapsort(PDF)(기술 보고서)의 최악의 경우번기입니다.MPI-INF. MPI-I-91-104.
  11. ^ a b Mehlhorn, Kurt; Sanders, Peter (2008). "Priority Queues" (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer. p. 142. ISBN 978-3-540-77977-3.
  12. ^ a b McDiarmid, C. J. H.; Reed, B. A. (September 1989). "Building heaps fast" (PDF). Journal of Algorithms. 10 (3): 352–365. doi:10.1016/0196-6774(89)90033-3.
  13. ^ a b MacKay, David J. C. (December 2005). "Heapsort, Quicksort, and Entropy". Retrieved 12 February 2021.
  14. ^ Moret, Bernard; Shapiro, Henry D. (1991). "8.6 Heapsort". Algorithms from P to NP Volume 1: Design and Efficiency. Benjamin/Cummings. p. 528. ISBN 0-8053-8008-6. For lack of a better name we call this enhanced program 'heapsort with bounce.'
  15. ^ a b Carlsson, Scante (March 1987). "A variant of heapsort with almost optimal number of comparisons" (PDF). Information Processing Letters. 24 (4): 247–250. doi:10.1016/0020-0190(87)90142-6. S2CID 28135103. Archived from the original (PDF) on 27 December 2016.
  16. ^ Wegener, Ingo (March 1992). "The worst case complexity of McDiarmid and Reed's variant of BOTTOM-UP HEAPSORT is less than n log n + 1.1n". Information and Computation. 97 (1): 86–96. doi:10.1016/0890-5401(92)90005-Z.
  17. ^ Tenenbaum, Aaron M.; Augenstein, Moshe J. (1981). "Chapter 8: Sorting". Data Structures Using Pascal. p. 405. ISBN 0-13-196501-8. Write a sorting routine similar to the heapsort except that it uses a ternary heap.
  18. ^ Cantone, Domenico; Concotti, Gianluca (1–3 March 2000). QuickHeapsort, an efficient mix of classical sorting algorithms. 4th Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science. Vol. 1767. Rome. pp. 150–162. ISBN 3-540-67159-5.
  19. ^ Cantone, Domenico; Concotti, Gianluca (August 2002). "QuickHeapsort, an efficient mix of classical sorting algorithms" (PDF). Theoretical Computer Science. 285 (1): 25–42. doi:10.1016/S0304-3975(01)00288-2. Zbl 1016.68042.
  20. ^ Diekert, Volker; Weiß, Armin (August 2016). "QuickHeapsort: Modifications and improved analysis". Theory of Computing Systems. 59 (2): 209–230. arXiv:1209.4214. doi:10.1007/s00224-015-9656-y. S2CID 792585.
  21. ^ Dijkstra, Edsger W. Smoothsort – an alternative to sorting in situ (EWD-796a) (PDF). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (설명)
  22. ^ Levcopoulos, Christos; Petersson, Ola (1989). "Heapsort—Adapted for Presorted Files". WADS '89: Proceedings of the Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science. Vol. 382. London, UK: Springer-Verlag. pp. 499–509. doi:10.1007/3-540-51542-9_41. ISBN 978-3-540-51542-5. Humpsort: 사전 정렬된 파일(Q56049336)에 적용됩니다.
  23. ^ Schwartz, Keith (27 December 2010). "CartesianTreeSort.hh". Archive of Interesting Code. Retrieved 5 March 2019.
  24. ^ Katajainen, Jyrki (23 September 2013). Seeking for the best priority queue: Lessons learnt. Algorithm Engineering (Seminar 13391). Dagstuhl. pp. 19–20, 24.
  25. ^ Katajainen, Jyrki (2–3 February 1998). The Ultimate Heapsort. Computing: the 4th Australasian Theory Symposium. Australian Computer Science Communications. Vol. 20, no. 3. Perth. pp. 87–96.
  26. ^ Morris, John (1998). "Comparing Quick and Heap Sorts". Data Structures and Algorithms (Lecture notes). University of Western Australia. Retrieved 12 February 2021.
  27. ^ https://github.com/torvalds/linux/blob/master/lib/sort.c Linux 커널 소스
  28. ^ Maus, Arne (14 May 2014). "Sorting by generating the sorting permutation, and the effect of caching on sorting". 6페이지의 그림 1을 참조하십시오.

레퍼런스

외부 링크

Wikibook Algorithm 구현 페이지에는 다음 항목이 있습니다.힙소트