Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
m (Another sync with the WP pseudocode) |
|||
| Line 757: | Line 757: | ||
end program Heapsort_Demo</lang> |
end program Heapsort_Demo</lang> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
Here's an ingenious solution that makes use of the heap module. Although the heap module usually implements an independent heap with push/pop operations, we use a helper type where the "pop" operation does not actually change the size of the underlying container, but changes a "heap length" variable indicating the length of the prefix of the underlying container that is considered "the heap". |
|||
Since we want to implement a generic algorithm, we accept an argument of type <code>sort.Interface</code>, and thus do not have access to the actual elements of the container we're sorting. We can only swap elements. This causes a problem for us when implementing the <code>Pop</code> method, as we can't actually return an element. The ingenious step is realizing that <code>heap.Pop()</code> must move the value to pop to the "end" of the heap area, because its interface only has access to a "Swap" function, and a "Pop" function that pops from the end. (It does not have the ability to pop a value at the beginning.) This is perfect because we precisely want to move the thing popped to the end and shrink the "heap area" by 1. Our "Pop" function returns nothing since we can't get the value, but don't actually need it. (We only need the swapping that it does for us.) |
|||
<lang go>package main |
<lang go>package main |
||
import |
import ( |
||
"sort" |
|||
"container/heap" |
|||
"fmt" |
|||
) |
|||
type HeapHelper struct { |
|||
| ⚫ | |||
container sort.Interface |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
} |
} |
||
func (self HeapHelper) Len() int { return self.length } |
|||
| ⚫ | |||
// We want a max-heap, hence reverse the comparison |
|||
for start := (len(a) - 2) / 2; start >= 0; start-- { |
|||
func (self HeapHelper) Less(i, j int) bool { return self.container.Less(j, i) } |
|||
siftDown(a, start, len(a)-1) |
|||
func (self HeapHelper) Swap(i, j int) { self.container.Swap(i, j) } |
|||
} |
|||
// this should not be called |
|||
for end := len(a) - 1; end > 0; end-- { |
|||
func (self *HeapHelper) Push(x interface{}) { panic("impossible") } |
|||
a[end], a[0] = a[0], a[end] |
|||
func (self *HeapHelper) Pop() interface{} { |
|||
siftDown(a, 0, end-1) |
|||
self.length-- |
|||
return nil // return value not used |
|||
} |
} |
||
| ⚫ | |||
helper := &HeapHelper{ a, a.Len() } |
|||
func siftDown(a []int, start, end int) { |
|||
heap.Init(helper) |
|||
for root := start; root*2+1 <= end; { |
|||
for helper.length > 0 { |
|||
child := root*2 + 1 |
|||
heap.Pop(helper) |
|||
if child+1 <= end && a[child] < a[child+1] { |
|||
child++ |
|||
| ⚫ | |||
if a[root] >= a[child] { |
|||
return |
|||
} |
|||
a[root], a[child] = a[child], a[root] |
|||
root = child |
|||
} |
} |
||
} |
|||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
| ⚫ | |||
}</lang> |
}</lang> |
||
Output: |
|||
More generic version that sorts anything that implements <code>sort.Interface</code>: |
|||
<pre> |
|||
before: [170 45 75 -90 -802 24 2 66] |
|||
after: [-802 -90 2 24 45 66 75 170] |
|||
</pre> |
|||
If you want to implement it manually: |
|||
<lang go>package main |
<lang go>package main |
||