A heap is a list where the following applies:

```
l[i] <= l[2*i] && l[i] <= [2*i+1]
```

for `0 <= i < len(list)`

I'm looking for in-place sorting.

Read the items off the top of the heap one by one. Basically what you have then is heap sort.

Well you are half way through a Heap Sort already, by having your data in a heap. You just need to implement the second part of the heap sort algorithm. This should be faster than using quicksort on the heap array.

If you are feeling brave you could have a go at implementing smoothsort, which is faster than heapsort for nearly-sorted data.

Sorting a heap in-place kind of sounds like a job for Heap Sort.

I assume memory is constrained, an embedded app, perhaps?

Just use heap-sort. It is in-place. That would be the most natural choice.

You can as well just use your heap as it and sort it with some other algorithm. Afterwards you re-build your heap from the sorted list. Quicksort is a good candidate because you can be sure it won't run in the worst-case O(n²) order simply because your heap is already pre-sorted.

That may be faster if your compare-function is expensive. Heap-sort tend to evaluate the compare-function quite often.

Since you already have a heap, couldn't you just use the second phase of the heap sort? It works in place and should be nice and efficient.

For in-place sorting, the fastest way follows. Beware of off-by-one errors in my code. Note that this method gives a reversed sorted list which needs to be unreversed in the final step. If you use a max-heap, this problem goes away.

The general idea is a neat one: swap the smallest element (at index 0) with the last element in the heap, bubble that element down until the heap property is restored, shrink the size of the heap by one and repeat.

This isn't the absolute fastest way for non-in-place sorting as David Mackay demonstrates http://users.aims.ac.za/~mackay/sorting/sorting.html">here - you can do better by putting an element more likely to be the smallest at the top of the heap instead of one from the bottom row.

Time complexity is T(n.log n) worst case - n iterations with possibly log n (the height of the heap) goes through the while loop.

```
for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
{
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
{
if (l[i] > l[left])
{
swapidx = left;
}
}
else
{
if (l[i] > l[right])
{
swapidx = right;
}
}
if (swapidx == i)
{
// Found right place in the heap, break.
break;
}
swap( l, i, swapidx );
i = swapidx;
}}
// Now reverse the list in linear time:
int s = 0;
int e = len(l)-1;
while (e > s)
{
swap( l, s, e );
s++; e--:
}
```

Similar Questions

I am looking for the fastest algorithm to sort numbers after FFT transformation - only real numbers in abs. values)=rational numbers in double precision, for 1d array of 2^19 elements. I think the meg

I am a little bit confused about what is the fastest and the friendly way with the server to request POST or GET from server by AJAX, is it jQuery ($.load(), $.get(), $.post(), $.ajax()) or Javascript

I would like to parse XML files into a MYSQL DB. What is the most efficient and fastest way to do this on a LINUX system (Ubuntu) and the least resource intensive. I have about 1GB worth of XML files

What's the fastest way to reverse a c-string, in place in c++ using only the library? In particular, are there any methods that require less than O(strlen) time?

for an array input 2 5 8 3 4 6 i am getting 2 4 5 3 8 6 i am trying to implement heap sort and i am a beginner and i don't know what error comes here and i am simply trying to implement the logic of h

What will be the fastest way to access an element from a collection? I am thinking should be in the order (low to high): Indexing an Array <= indexing a collection/list <= use key on Dictionary

I have a video which is represented as AVURLAsset. It comes from Camera Roll and is at full resolution. Now if I only need it with 380 pixels width, what would be the fastest and most efficient way to

I have n strings, each of length n. I wish to sort them in ascending order. The best algorithm I can think of is n^2 log n, which is quick sort. (Comparing two strings takes O(n) time). The challenge

I have a large matrix: set.seed(1) a <- matrix(runif(9e+07),ncol=300) I want to sort each row in the matrix: > system.time(sorted <- t(apply(a,1,sort))) user system elapsed 42.48 3.40 45.88

This question already has an answer here: Merge two lists in Python? 11 answers Given, list_1 = [1,2,3,4] list_2 = [5,6,7,8] What is the fastest way to achieve the following in python? list =

I've looked over a few implementations of Fibonacci function in Scala starting from a very simple one, to the more complicated ones. I'm not entirely sure which one is the fastest. I'm leaning towards

What is the fastest way to deploy a Java HttpServlet? Is there a solution that allows you to do it very quickly like I could do in Ruby/PHP/Python with minimal configuration? I need something that wil

There seems to be a handful of JSON libraries out there for Python even though Python has a built-in library. One even claims to be built according to http://www.json.org spec (which caused me to thin

Answering to another Stack Overflow question (this one) I stumbled upon an interesting sub-problem. What is the fastest way to sort an array of 6 ints? As the question is very low level: we can't ass

Okay, so after struggling with trying to debug this, I have finally given up. I'm a beginner in C++ & Data Structures and I'm trying to implement Heap Sort in C++. The code that follows gives corr

The guys at the top want sort order to be customizable in our app. So I have a table that effectively defines the data type. What is the best way to store our sort order. If I just created a new colum

Fastest way to find the index of the second (third...) highest/lowest value in vector or column ? i.e. what sort(x,partial=n-1)[n-1] is to max() but for which.max() Best, Fastest way to find seco

I have a List (Foo) and I want to see if it's equal to another List (foo). What is the fastest way ?

I need to serialize DataFrames and send them over the wire. For security reasons, I cannot use pickle. What would be the next fastest way to do this? I was intrigued by msgpacks in v0.13, but unless I

My application will call Facebook API multiple times: the example. What is the fastest / most reliable way to send HTTP GET requests and parse the returned output in JSON format? Should I use Curl::Ea

What is the fastest way to learn maven? I am up to speed with it but can't keep up with its idiosyncrasies. Any idea?

What is the fastest way to implement something like this in C#: private List<string> _myMatches = new List<string>(){one,two,three}; private bool Exists(string foo) { return _myMatc

What is the fastest way to calculate angle between a line and the x-axis? I need to define a function, which is Injective at the PI:2PI interval (I have to angle between point which is the uppermost p

What is the fastest way to check the content type of a list item in SharePoint 2010 when all I have is the SiteId (site collection) and ItemId (the GUID)? (I also have the SPSite instance) I am readin

I know iOS 5.0 has Twitter integration, but what's the fastest way to implement a follow us button in an iOS 4.0 compatible app? Of course it is not a good idea to simply open a http://... to twitte

I have a data file of almost 9 million lines (soon to be more than 500 million lines) and I'm looking for the fastest way to read it in. The five aligned columns are padded and separated by spaces, so

I would like to know what is the fastest way to read Thumbnail of a video? My problem is that I've had a couple of videos files and I need to get the thumbnail from all of them. For now I'm using : th

What is the fastest and most efficient way to create XML documents in Java? There is a plethora of libraries out there (woodstox, xom, xstream...), just wondering if any one has any input. Should I go

What is the fastest way to compute absolute value of integer of long long int type in C++ ? Is it possible to do without if() statement ? I was trying conversion to unsigned and then to signed again,

What is the fastest way to get the last key/value pair of an associative array in PHP? I know there are some wordy ways to do this. But what's the most concise and efficient way?

What is the fastest way to populate a SQLite database from a DataTable in C# .net 2. Currently I am building insert statments for each row in the table. I have tried a dataadaptor but the speed didn't

What's the fastest way to send a file over UDP? A) Create a large datagram for each chunk of the file, send that, and wait for a acknowledgement from the client before continuing B) Create a large dat

In heap sort algorithm n=m for k:= m div 2 down to 0 downheap(k); repeat t:=a[0] a[0]:=a[n-1] a[n-1]:=t n— downheap(0); until n <= 0 Can some one please explain to me what is done in lines n=m

What is the fastest way to zero out an unsigned int? I am currently just setting the value to 0, but I don't know if there are any tricks for zeroing out a variable? I need a few clock cycles back in

Using PHP, what's the fastest way to convert a string like this: 123 to an integer? Why is that particular method the fastest? What happens if it gets unexpected input, such as hello or an array?

Is there an alternative way to sort a JSON file or at least, a drop-down list other than this following code? json.sort(function(a, b){ return a.id - b.id; }); The reason for this is that it takes so

I tried Junit @Theory test style recently : it's a really efficient way of testing. However, i not pleased with the exception that are thrown when a test fails. Example : import static org.junit.Asser

I want to read files of the magnitude of GB's (like say 10 GB). What is the fastest way to read such a file in C. I am trying to do an implementation of tail but I think I/O can be a bottleneck. Any s

Possible Duplicate: What is the best way to do loops in JavaScript What’s the best way to loop through a set of elements in JavaScript? Any ideas?

I'm trying to determine what is the fastest way to implement this code: Pattern ID_REGEX = Pattern.compile( [A-Za-z0-9_\\-.]+ ); boolean match = ID_REGEX.matcher( id ).matches(); if ( !match ) throw

What is the fastest and most efficient way to check for Internet connectivity in .NET?

I am implementing Heap Sort for an assignment. We have to do it the same way she did in class with her pseudocode, or else we dont get credit. In my Max_Heapify function, im getting an error when I ca

What is the fastest (smaller code) way to get grammar tree ? I am trying to get grammar tree. I've generated C# code based on my simple grammar: grammar MyPascal; options { language=CSharp3; output=AS

I writting assignment about heap sort in php. I am in a little bit difficult situation. Please help me. Any one who suggest me the code. Thanks in advance.

What is the best and fastest way to check if the image is valid in PHP ? I need it to be able to check GIF, JPG as well as PNG images.

My application is a real-time apps using ajax environment. It is a live picking of schedule. The users want see the available slot in real-time way. such that they can see other ticking schedule. And

I like the convenience of NSMutableArray but sometimes you just need to drop down to good ole C-arrays. Like when you are feeding interleaved vertex arrays to OpenGL. What is the fastest way of copyin

What is the fastest way to remove duplicate character in a string without using an extra memory in Java?

What's the fastest way to register a java-application (or maybe a bat executing the app) as a Windows service? Update 1: It has to be free for companies to execute :) Either by using a third party app

what is the fastest way to find the greatest common divisor of n numbers other than using gcd(a,b,c)=gcd(gcd(a,b),c).