kenics.net

Technical notes on perl, python, php, sql, cgi, c/c++, q/kdb+, unix/shell, revision control tools, data structures & algorithms, and their applications into web services and other various forms of software engineering.

heap sort

 
######################## 
####   heap sort    #### 
######################## 
 
read the heap data structure article. 
 
heap sort is essentially popping the root till the heap is empty. 
 
e.g. 
 
while(!heap.isEmpty()) 
   heap.deleteMin(); 
 
 
 
######################### 
####   complexity    #### 
######################### 
 
## time 
 
worst case   : O(n log n) 
average case : O(n log n) 
best case    : O(n) 
 
worst case is when you pop a root, and the arr[lastElem] you bring to the top needs to bubble down to the bottom again, which is log N depth operation. 
and you pop N elements. hence O(n log n) 
 
average case is when you consider a uniform distribution of the input, which still gives you (log n)/2 depth times N pop operations, thus still O(n log n) 
 
best case is when you have an already sorted input, depth is always 1 times N pop operations, thus O(n) 
 
 
## space 
 
total     : O(n) 
auxiliary : O(1) 
 
no extra space needed as delineated in the implementation example. because the input array itself can be treated as a heap. 
 
 
########################################### 
####   implementation example in C++   #### 
########################################### 
 
read the heap data structure article 
 

  1. 2014-06-23 23:47:06 |
  2. Category : misc
  3. Page View:

Google Ads