Skew heap

예전에 남부순환로 문제를 출제할 때 Mergeable heap에 관해서 사람들과 논의하던 때가 있었는데, Leftist heap / Randomized mergeable heap 모두 딱 와닿는 느낌의 논증은 없었던 것 같다. 최근에 Skew heap이라는 걸 접했는데 굉장히 짧고 아름다운 논증이 존재해서 소개한다. (아쉽게도 Worst-case bound가 아니라 남부순환로 문제에는 사용할 수 없다. 이론적으로는.)

목표는 Merge 연산을 Amortized $O(\log n)$ 에 수행하는 것이다. 이것만 수행하면 Init, ExtractMin은 따라온다.

두 트리를 머지할때 오른쪽 자식을 따라서 path를 타고 가자. 이 path를 따라 적힌 값들은 증가한다. 고로 이 path를 따라서 merge sort하듯이 merge하면 올바른 힙을 얻는다.

이것만 하면 어떤 노드에도 왼쪽 자식이 존재하지 않는 path 형태의 heap이 될 테니, 이 연산을 하고 나서 path에 있는 모든 노드의 왼쪽/오른쪽 child를 바꿔주자. 고로, 오른쪽으로 타고 내려가던 path가 이제 왼쪽으로 타고 내려가는 path가 될 것이다.

알고리즘의 정당성은 자명하다. 이제 Merge 연산의 시간 복잡도만 증명하면 된다. 어떠한 노드가 왼쪽 편향 되었다는 것을, 왼쪽 자식의 크기가 오른쪽 자식의 크기 이상이라는 것으로 정의하자. (오른쪽 편향 은 그 반대). Merge를 진행한 후, 오른쪽 자식을 따라 내려가면 왼쪽 편향된 노드는 $\log_2 n$ 개밖에 없다. 왼쪽 편향된 노드는 오른쪽 경로 상의 힙의 크기를 반으로 줄이기 때문이다. 이 트리의 경로를 뒤집으면, 오른쪽 편향된 노드는 최대 $\log_2 n$ 개 생긴다.

고로, Merge 연산의 과정은

• Merge sort하듯이 두 힙을 합쳐준다. 오른쪽 편향된 노드가 여러개 생긴다. 왼쪽 편향된 노드는 0개 생긴다.
• 경로를 뒤집는다. 아까 만든 오른쪽 편향된 노드는 모두 왼쪽 편향된다. 원래 왼쪽 편향이었던 노드들만 오른쪽 편향되고, 이러한 노드들은 최대 $\log_2 n$ 개 만든다고 볼 수 있다.

이니 이 과정에서 새로 생긴 오른쪽 편향된 노드는 $O(\log_2 n)$ 개이다. Merge 연산에서 사용한 연산 비용은, 원래 두 힙의 (path 상 오른쪽 편향된 노드 합) + (path 상 왼쪽 편향된 노드 합) 과 동일하다. 후자의 비용은 $O(\log n)$ 이다. 전자의 비용은 오른쪽 편향된 노드가 새로 발생할 때 치르면 된다.

왼쪽 편향, 오른쪽 편향 의 논리가 Light Edge, Heavy Edge 의 논리와 동일함을 관찰하면 좋다.