Classic Heap Sort

View previous topic View next topic Go down

Classic Heap Sort

Post  viterbi on Thu Sep 08, 2011 10:58 am

I think Java should have the equivalent of priority_queue, please try it anyway.

1____void my_hsort2(int* a, int N) {
2__________priority_queue<int> v;
3__________for (int i=0; i<N; i++) v.push(-a[i]);
4__________for (int i=0; i<N; i++) {
5________________a[i] = -v.top();
6________________v.pop();
7__________}
8____}

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Re: Classic Heap Sort

Post  Admin on Thu Sep 08, 2011 2:11 pm

Yes, Java also has priority queue.

In Java, Priority Queue is implemented by Complete Binary Tree, which to use an array to store all elements.

Node at position i in the array
Children at positions 2i and 2i+1

When inserting a node, it needs to guarantee the heap order property

Admin
Admin

Posts : 131
Join date : 2011-08-16

View user profile http://codefornongeek.forumotion.com

Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum