heapSort.go

/*
build heap :
max node num in hight h is n/2^(h+1), max h is lgn,
T(n) = n*sum(0/2+1/2^1+...+lgn/2^(lgn+1))= (n/2)*sum(2/2^1+...+lgn/2^lgn)
=(n/2)*(2-((lgn+2)/2^(lgn))) <= (n/2)*2=n
d heap:
n*(d-1)/d^(h+1), max h is logd((d-1)n), T(n) = (n*(d-1)/d) *sum(1/d^1+2/d^2+...logd((d-1)n)/d^logd(d-1)n)
= (n*(d-1)/d) <= O(n)

about golang slice:
a := []int{...}
b := a

b and a point to the same memory, but are different object.
so they both can modify shared data.But they have different lenth,index and so on
*/

package sort

import (
"github.com/shady831213/algorithms/heap"
)

funcheapSort(arr []int) {
h:=heap.NewHeapIntArray(arr)
fori:=h.Len() -1; i>0; i-- {
h.Pop()
 }
}

/*not generic heap*/
typeintArrayForHeapSort []int

func (h*intArrayForHeapSort) parent(iint) int {
returni>>1
}
func (h*intArrayForHeapSort) left(iint) int {
return (i<<1) +1
}
func (h*intArrayForHeapSort) right(iint) int {
return (i<<1) +2
}

func (h*intArrayForHeapSort) maxHeaplify(iint) {
largest, largestIdx:= (*h)[i], i
if (*h).left(i) <len((*h)) && (*h)[(*h).left(i)] >largest {
largest, largestIdx= (*h)[(*h).left(i)], (*h).left(i)
 }
ifh.right(i) <len((*h)) && (*h)[h.right(i)] >largest {
_, largestIdx= (*h)[h.right(i)], h.right(i)
 }
ifi!=largestIdx {
 (*h)[largestIdx], (*h)[i] = (*h)[i], (*h)[largestIdx]
h.maxHeaplify(largestIdx)
 }
}

func (h*intArrayForHeapSort) buildHeap() {
fori:= (len((*h)) >>1) -1; i>=0; i-- {
h.maxHeaplify(i)
 }
}

funcheapSort2(arr []int) {
h:=intArrayForHeapSort(arr)
h.buildHeap()
fori:=len(h) -1; i>0; i-- {
h[0], h[i] =h[i], h[0]
h=h[:i]
h.maxHeaplify(0)
 }
}