1-ary heap sort?

Question

A while back we were given an assignment to write a c program that sorts an array of n numbers using a d-ary max-heap (a heap where each node has up to d children). The program needed to ask the user to input the value of d, a value between 2 and the size of the array. While I was checking my program I accidentally entered 1 as the value of d, and somehow the algorithm succeeded in sorting the array correctly using a 1-ary heap, although it took alot more time than normal values of d.

How is that possible? A 1-ary heap isn't even a heap it's just like a list, every node has only one child. Can anyone explain how this sorting could happen?

Douala

Answer 1

An 1-ary heap is still a heap, and satisfies all the invariants that are required by a heap sort:

• The first element is the largest element.
• Percolation can move the top element down to its correct position.

In practice, an 1-ary heap is a tree where every node has one child - this is also known as a singly linked list. Also, the heap constraint means the child node is smaller than the parent node. So, simply put, an 1-ary heap is a singly linked list sorted in reverse order.

Constructing the heap in the first place is equivalent to an insertion sort (percolate all items into the list one by one). Once this is done, removing the first element yields the largest element of all, and the subsequent percolation moves every item in the list up by one level.

Insomnia

so what actually happened is an in-efficient variant of insertion sort? – Douala

It was a standard insertion sort, followed by a series of "pop" operations that involved moving all elements in the heap from "n" to "n-1". – Insomnia