Re: HEAP SORT
Once you understand the data structure "binary heap" and its main
operations insert() and extract_{min|max}(), it is pretty
straightforward to construct "heap sort" out of it: To sort 'n'
elements, insert them into the heap (n*insert) and then extract the
root (min or max) 'n' times to get the elements in sorted order. The
running time can be derived directly from the running time of those two
heap operations. [Btw. it is also possible to build a heap in linear
time]
Chris
.
Relevant Pages
- Re: Binary heaps
... > size N with a binary heap of size log N. Can a binary heap support ... > LOG-HEAP UNION, INSERT and EXTRACT-MIN each in Otime? ... There are only Osuch cells. ...
(comp.theory) - Re: Advice on data structure for scheduled events
... putting each event into an appropriate bucket (that holds all events ... strategy (for a naive vector, adding a new element occassionally takes ... What sort of heap? ... Googmeister suggested a binary heap, ...
(comp.programming) - Re: Proof that this assertion about heaps is true
... assuming the particular implementation is a binary heap and the ... I suppose to guarantee I am okay I'll have to write my own heap ... >> will definitly restore the heap by definition. ... > the requirements of the standard. ...
(comp.theory) - Re: Binary heaps
... > size N with a binary heap of size log N. Can a binary heap support ... > LOG-HEAP UNION, INSERT and EXTRACT-MIN each in Otime? ... it will join them in linear time. ...
(comp.theory) - Re: sorting just the largest values
... >code (using a mythical module Heap, but there are real ones on CPAN): ... >use an external counter instead. ... >If $n is larger than the data size, the algorithm does a heap sort on ...
(comp.lang.perl.misc) |
|
