약한 힙

Weak heap

컴퓨터 과학에서 약한 힙은 이진 힙과 이항 힙의 기능을 결합한 우선 순위 대기열의 데이터 구조다.이진 힙과 같은 암시적 이진 트리로서 배열에 저장할 수 있으며, 이항 힙의 효율적 보증을 가지고 있다.

약한 힙, 약한 힙을 사용하는 정렬 알고리즘은 목록을 정렬하는 데 필요한 비교 횟수에 이론적인 하한에 가까운 다수의 비교를 사용하므로 전체 유니코드 결합 알고리즘을 사용하여 문자열을 비교할 때 등 비교 비용이 많이 들 때 특히 유용하다.

설명

약한 힙은 "우차일드 좌시블링" 규칙을 사용하여 이진 트리로 저장된 힙 순서 다방향 트리로 가장 쉽게 이해된다.(이것은 보통의 좌-자녀 우-시블링 바이너리 트리와 같으나 반대로 된다.)

다원 트리에서, 그리고 최대 히프를 가정했을 때, 각 부모의 키는 모든 자식 키(따라서 유도에 의해, 하위 트리의 모든 멤버)보다 크거나 같다.

2진수 트리로 표현되며, 이는 다음과 같은 불변수로 해석된다.[1]

  • 루트 노드에 왼쪽 하위 노드가 없음
  • 모든 노드에 대해, 그 노드와 관련된 값은 오른쪽 하위 트리의 모든 노드와 연관된 값보다 크거나 같다.
  • 그 나무의 잎들은 모두 서로 안에 있는 높이들을 가지고 있다.

마지막 조건은 암묵적인 이진 트리가 완전한 이진 트리라는 사실의 결과물이다.

이 트리의 구조는 전통적인 1-기반(아넨타펠) 암묵적 이진수 배열로 매우 깔끔하게 맵핑되는데, 노드 k는 다음 형제(왼쪽 아이)가 2k, 첫 번째 자식(오른쪽 아이)은 0의 루트를 더하여 2k + 1의 번호를 갖는다.이 루트에는 형제자매가 없고 첫 번째 아이만 있는데, 노드 1(2×0 + 1)이다.

이 구조는 이항 더미에 높이 h의 나무 높이 h− 1, h− 2,..., 1.2n 요소와 완벽한( 없는 실종된 잎) 약한 더미 같은 size,[2]의 이항 힙에 동형은의 뿌리와 나무들로 구성되어 있지만 두가지 알고리즘 2이 아닌 권력 다르게 크기를 다루는:a. 비슷하다 binomial 힙은 여러 개의 완벽한 나무를 사용하는 반면, 약한 힙은 하나의 불완전한 나무를 사용한다.

약한 힙을 사용하려면 노드의 왼쪽과 오른쪽 자식(및 관련 하위 트리)을 교환할 수 있는 기능이 필요하다.트리의 명시적(점자 기반) 표현에서 이것은 간단하다.암묵적(배열적) 표현에서 이것은 어떤 아이가 왼쪽 아이로 간주되는지를 나타내기 위해 내부 노드당 하나의 "역방향 비트"를 필요로 한다.따라서 취약한 힙은 O(n)의 추가 공간이 필요하기 때문에 엄격하게 암시적인 데이터 구조가 아니다.노드당 1/2비트).그러나 이미 존재하는 포인터에 태그를 지정하여 노드 구조 내에서 이 추가 비트를 위한 공간을 찾을 수 있는 경우가 많다.

암시적 이진수 트리에서 역비트 r이k 있는 노드 k는 상위 ⌊k/2⌋, 왼쪽 하위 2k + rk, 오른쪽 하위 2k + 1 - r을k 갖는다.

다원 트리로 보아 약한 힙의 각 노드는 "다음 형제"와 "첫 번째 자식"의 다른 두 개와 연결된다.암시적 트리에서 링크는 고정되어 있으므로, 두 링크 중 어느 것이 형제자매인지, 어떤 것이 첫 번째 아이가 역비트로 표시되는지 알 수 있다.

약한 무더기 작전

약한 힙의 모든 노드는 다음 형제자매를 무시하면 더 작은 약한 힙의 루트로 간주될 수 있다는 점에 유의하십시오.첫째 아이가 없는 노드는 자동으로 유효성이 약한 힙이다.

높이 h의 한 노드는 h - 1자녀: 키 h - 1, 키 h - 2의 둘째 아이, 키 1의 마지막 아이 등으로 구성된다.첫 번째 자식 링크를 따라간 다음 다음 형제 링크를 통해 이러한 정보를 찾을 수 있다.

또한 키 h - 1, h - 2 등의 다음 형제자매가 있다.

다방향 트리에 있는 노드의 부모를 "변화된 조상"이라고 부른다.이진 트리에서 이 값을 찾으려면 노드의 이진 상위 항목을 찾으십시오.노드가 올바른 자식(첫 번째 자식)인 경우, 부모는 구별된 조상이다.노드가 왼쪽 자식(다음 형제)인 경우, 노드의 고유 조상은 이진 부모의 조상과 동일하다.암묵적 트리에서, 바이너리 부모를 찾는 것은 쉽지만, 그 역비트를 참고하여 노드가 어떤 유형의 아이인지를 결정해야 한다.(초기 논문에서는 "조상"이라는 용어를 사용했는데,[3] 이는 일반적인 "부모의 부모"와는 혼동되게 다른 의미였다.)

비록 뛰어난 조상은 나무에서 높은 로그2 수준일 수 있지만 평균 거리는 2. (적어도 1이고, 우리가 재발하는 시간의 절반이므로 D = 1 + D/2를 의미함)따라서 뛰어난 조상을 찾기 위한 단순한 반복 알고리즘으로도 충분하다.

이항 히프처럼, 약한 힙에 대한 근본적인 수술은 같은 높이 h의 두 힙을 합쳐 약한 높이 h+1의 힙을 만드는 것이다.이것은 정확히 하나의 비교를 필요로 한다, 뿌리 사이의.어느 루트가 더 큰지(최대 히프를 가정)가 최종 루트다.그것의 첫 번째 아이는 잃어버린 뿌리인데, 그 뿌리는 자식들을 간직하고 있다(오른쪽 하위 트리.당첨 뿌리의 자녀는 잃어버린 뿌리의 형제자매로 설치된다.

이 작업은 병합되는 힙이 절대 임의적이지 않기 때문에 암시적 트리 구조에서 수행될 수 있다.오히려, 이 두 개의 힙은 다원 트리 위로 노드를 체로 치환하는 것의 일부로 형성된다.

  • 첫 번째는 정상적인 약한 힙(다음 형제 링크가 존재하지만 무시되는 경우)이다.
  • 두 번째는 첫 번째 뿌리의 구별되는 조상(다중방향 부모)을 첫 번째 뿌리의 뒤따르는 형제자매와 연결시켜 형성된 가상의 힙이다.

처음에는 첫 번째 뿌리와 그 뛰어난 조상 사이에 있을 수 있는 것을 제외한 모든 곳에 힙 불변제가 적용된다.다른 모든 노드는 그들의 뛰어난 조상보다 작거나 같다.

두 근을 비교한 후 합병은 다음 두 가지 방법 중 하나로 진행된다.

  1. (유명한 조상이 더 크거나 같음)아무것도 움직일 필요가 없고, 합병의 결과는 뛰어난 조상이다.
  2. (첫 번째 뿌리가 더 크다.)첫 번째 뿌리의 바이너리 자식(첫째 아이와 다음 형제자매)을 교환한 다음(역비트를 사용하여), 첫 번째 뿌리와 그 구별되는 조상(복사)을 교환한다.

두 번째 사례는, 다원 트리에서는, 각각의 노드가 아이들을 그것과 함께 보관하기 때문에 효과가 있다.첫 번째 뿌리는 그 뛰어난 조상보다 크기 때문에 나무 위로 승격된다.따라서, 그것은 조상의 모든 이전의 아이들보다 안전하게 더 크다.

그러나 이전의 조상은 첫 번째 뿌리보다 작아서 모든 자식보다 크거나 동등하다고 보장되지 않기 때문에 첫 번째 뿌리의 늙은 자식들에게는 안전한 부모가 아니다.

이항아리를 스와핑함으로써 강등된 조상의 노자(안전하게 그것보다 작거나 같음)의 적절한 하위집합이 그것과 함께 강등된다.강등된 조상의 새 형제자매는 제1근의 노자녀로, 제1근의 노자녀로서 안전하게 제1근보다 적거나 동등하다.

이 수술 후, 새로운 유공 조상과 그 유공 조상의 사이에 불변제가 유지되는지 여부가 불확실하므로 뿌리에 도달할 때까지 수술을 반복한다.

약한 heap 분류

약한 힙은 배열의 분류에 사용될 수 있으며, 기본적으로 기존의 힙포트와 같은 방식으로 사용될 수 있다.[3]먼저 배열의 모든 원소로 약한 힙을 쌓은 다음, 마지막 원소와 반복적으로 근을 교환하여 적당한 위치로 체로 내린다.

n개 원소의 약한 힙은 n - 1 병합으로 형성될 수 있다.다양한 주문으로 할 수 있지만, 간단한 상향식 구현이 어레이의 끝에서 시작까지 작동하여 각 노드를 그 뛰어난 조상과 병합한다.병합되는 힙의 모든 부모에서 역비트가 초기 상태("역비트가 아님")에서 수정되지 않기 때문에 구별된 조상을 찾는 것이 단순화되므로 참조할 필요가 없다는 점에 유의하십시오.

heapsort와 마찬가지로, 정렬할 어레이가 CPU 캐시보다 크면, 다음 단계로 진행하기 전에 한 레벨의 모든 하위 트리를 병합하는 것이 아니라, 동일한 크기의 두 개의 하위 트리를 사용할 수 있게 되는 즉시 하위 트리를 병합하면 성능이 향상된다.[4]

약한 힙에서 아래로 처리는 이진 힙의 경우 2 logn2 또는 "bottom-up heapsort" 변종의 경우 1.5 logn이2 아닌 h = ⌈logn2⌉ 비교로 수행할 수 있다.이 작업은 "merging up"을 통해 수행되며, 힙의 마지막 요소와 루트를 스와핑한 후 루트의 마지막(높이 1) 자식을 찾으십시오.이 값을 루트(특수 상위 항목)와 병합하여 글로벌 루트에 유효한 높이-2 힙을 생성하십시오.그런 다음 마지막으로 병합된 노드의 이전 형제(이진 부모)로 이동한 후 다시 병합하십시오.루트에 도달할 때까지 반복하여 완전한 트리에 적합할 때까지 반복하십시오.

우선 순위 대기열 작업

약한 max-heap에서는 루트 노드와 관련된 값으로 최대값을 찾을 수 있고(정규 시간 내에), 마찬가지로 약한 min-heap에서는 최소값을 루트에서 찾을 수 있다.

이진 힙과 마찬가지로, 약한 힙은 우선순위 대기열 데이터 구조(삽입, 삭제 최소, 삭제 또는 감소 키)의 일반적인 작동을 작업당 로그 시간으로 지원할 수 있다.

체프 업은 이진 힙에서와 동일한 프로세스를 사용하여 이루어진다.새 노드는 리프 레벨에서 추가된 후, 그 뛰어난 조상들과 비교하고 필요한 경우 교환한다(합병 작업).더 이상 스와프가 필요 없거나 루트에 도달할 때까지 반복한다.

약한 힙 구조의 변형들은 피보나치 힙의 시간과 일치하도록 지속적으로 상각된 시간 삽입과 감소키를 허용한다.[2]

기록 및 응용 프로그램

약한 힙은 (이진 힙을 사용한 표준 힙 정렬과는 달리) n2 logn + O(n) 비교만 사용하여 n개 항목을 정렬하는 데 사용할 수 있는 변형 힙 정렬 알고리즘의 일부로 듀튼(1993)에 의해 도입되었다.[3][5]그들은 나중에 보다 일반적으로 적용 가능한 우선 순위 대기열 데이터 구조로 조사되었다.[6][7]

참조

  1. ^ Edelkamp, Stefan (26 May 2011), Pieterse, Vreda; Black, Paul E. (eds.), "weak-heap", Dictionary of Algorithms and Data Structures, retrieved 2015-12-01
  2. ^ a b Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (October 2012), "The weak-heap data structure: variants and applications" (PDF), Journal of Discrete Algorithms, 16: 187–205, CiteSeerX 10.1.1.455.1213, doi:10.1016/j.jda.2012.04.010, MR 2960353.
  3. ^ a b c Dutton, Ronald D. (1993), "Weak-heap sort", BIT, 33 (3): 372–381, doi:10.1007/bf01990520.
  4. ^ Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). "Performance Engineering Case Study: Heap Construction" (PostScript). ACM Journal of Experimental Algorithmics. 5 (15). CiteSeerX 10.1.1.35.3248. doi:10.1145/351827.384257. 대체 PDF 원본.
  5. ^ Edelkamp, Stefan; Wegener, Ingo (2000), "On the performance of WEAK-HEAPSORT", Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2000) (PDF), Lecture Notes in Computer Science, vol. 1770, Springer-Verlag, pp. 254–266, CiteSeerX 10.1.1.21.1863, doi:10.1007/3-540-46541-3_21.
  6. ^ Bruun, Asger, Edelkamp, 스테판, Katajainen, Jyrki;라스무센, 옌스(2010년)."Policy-Based 벤치마킹으로 Heaps의 개발과 Relatives"(PDF).9일 국제 심포지엄 실험적 이론을 회보(SEA2010년).강의 노트 컴퓨터 과학으로.Vol6049.Springer-Verlag.를 대신하여 서명함. 424–435. doi:10.1007/978-3-642-13193-6_36.아이 에스비엔 3-642-13192-1.2017-08-11.에 있는 원본(PDF)에서 Archived.
  7. ^ Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2012), "The Weak-heap Family of Priority Queues in Theory and Praxis" (PDF), Proceedings of the Eighteenth Computing: The Australasian Theory Symposium (CATS 2012), vol. 128, Darlinghurst, Australia: Australian Computer Society, Inc., pp. 103–112, ISBN 978-1-921770-09-8.

추가 읽기

  • Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (November 2013). "Weak heaps engineered" (PDF). Journal of Discrete Algorithms. 23: 83–97. doi:10.1016/j.jda.2013.07.002. We provide a catalogue of algorithms that optimize the standard algorithms in various ways. As the optimization criteria, we consider the worst-case running time, the number of instructions, branch mispredictions, cache misses, element comparisons, and element moves.
  • Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki; Weiß, Armin (July 2013). Weak Heaps and Friends: Recent Developments (PDF). Combinatorial Algorithms - 24th International Workshop. Rouen, France. doi:10.1007/978-3-642-45278-9_1.