There are a number of Haskell heap implementations in an appendix to Okasaki’s Purely Functional Data Structures (pdf). (The source code can be downloaded at the link. The book itself is well worth reading.) None of them are binary heaps, per se, but the “leftist” heap is very similar. It has O(log n) insertion, removal, … Read more
Heap sort unstable example Consider array 21 20a 20b 12 11 8 7 (already in max-heap format) here 20a = 20b just to differentiate the order we represent them as 20a and 20b While heapsort first 21 is removed and placed in the last index then 20a is removed and placed in last but one … Read more
Right, so basically you take a heap and pull out the first node in the heap – as the first node is guaranteed to be the largest / smallest depending on the direction of sort. The tricky thing is re-balancing / creating the heap in the first place. Two steps were required for me to … Read more
One of the major factors is that quicksort has better locality of reference — the next thing to be accessed is usually close in memory to the thing you just looked at. By contrast, heapsort jumps around significantly more. Since things that are close together will likely be cached together, quicksort tends to be faster. … Read more
A stable sort maintains the relative order of items that have the same key. For example, imagine your data set contains records with an employee id and a name. The initial order is: 1, Jim 2, George 3, Jim 4, Sally 5, George You want to sort by name. A stable sort will arrange the … Read more