1-ary 힙 정렬?

Question

d-ary max-heap (각 노드가 최대 d 개의 자식을 갖는 힙)을 사용하여 n 개의 숫자 배열을 정렬하는 c 프로그램을 작성하는 과제가있었습니다. 이 프로그램은 사용자에게 d의 값, 2와 배열의 크기 사이의 값을 입력하도록 요청해야했습니다. 내 프로그램을 검사하는 동안 우연히 d의 값으로 1을 입력했는데 d의 정상 값보다 많은 시간이 걸렸지 만 알고리즘은 1-ary 힙을 사용하여 배열을 올바르게 정렬하는 데 성공했습니다.

어떻게 가능합니까? 1-ary 힙은 목록과 같은 힙이 아니며 모든 노드에는 하나의 자식 만 있습니다. 누구든지이 정렬이 일어날 수있는 방법을 설명 할 수 있습니까?

Answer 1

1 진 힙은 여전히 ​​힙, 그리고 만족 힙 정렬에 필요한 모든 불변 :

• 첫 번째 요소는 가장 큰 요소입니다.
• 퍼콜 레이션을 사용하면 상단 요소를 올바른 위치로 이동할 수 있습니다.

실제로 1-ary 힙은 모든 노드에 하나의 자식이있는 트리입니다. 이것은 단일 연결 목록이라고도합니다. 또한 힙 제약 조건은 자식 노드가 부모 노드보다 작다는 것을 의미합니다. 간단히 말하면, 1-ary 힙은 역순으로 정렬 된 단일 연결 목록입니다.

처음부터 힙을 작성하는 것은 삽입 정렬 (모든 항목을 목록에 하나씩 차례로 이동)과 동일합니다. 이 작업이 끝나면 첫 번째 요소를 제거하면 all의 가장 큰 요소가 나오고 이후의 침투는 목록의 모든 항목을 한 수준 위로 이동합니다.