Timeline for java heapify method with comparator
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 14, 2015 at 6:13 | comment | added | Jason Nordwick | It only looks that way, but each pass orders the tree more and more. geeksforgeeks.org/g-fact-85 | |
| Jan 14, 2015 at 6:09 | comment | added | Pham Trung | Your time complexity is log(n) + log(n-1) + ... + log 1 = log(n*(n-1)*(n-2)...) = log(n!) ~ O(n log n). More info | |
| Jan 14, 2015 at 5:56 | comment | added | Pham Trung |
For each heapifyDown, I see that it needs to travel O(log n) from top to bottom, which basically is O(nlogn), however, this is not a tight bound, can you provide a mathematical prove that this is O(n)?
|
|
| Jan 14, 2015 at 5:15 | history | edited | Jason Nordwick | CC BY-SA 3.0 |
clearer
|
| Jan 14, 2015 at 5:11 | vote | accept | lorantalas | ||
| Jan 14, 2015 at 5:11 | |||||
| Jan 14, 2015 at 5:09 | history | answered | Jason Nordwick | CC BY-SA 3.0 |