## Sunday, November 1, 2015

### median heaps and a sorting method

Suppose you have a list of some sortable items indexed naturally starting at 1:
L=2,4,7,9,3,1,5,8,6
Imagine building a heap but not a max heap or a min heap but a median heap, where the property is that position n is greater than or equal to position 2*n and less than or equal to position 2*n+1. Or thinking of it as a tree, that the left child is less than or equal to the parent which is less than or equal to the right child... So looking at the above list:

H=2,4,7
H(1)=2, H(2)=4, H(3)=7 so this does not yet have the property that H(2*n) <= H(n) <= H(2*n+1) for n=1
so we rearrange those 3 items so the property is true:
4,2,7
Now the property is satisfied so we add two more numbers from the list
4,2,7,9,3
H(2) =2 H(4)=9 H(5)=3 so we have to rearrange those three numbers to satisfy the property
4,3,7,2,9
Now since H(2) changed we have to again see whether H(2)<= H(1) <=H(3) which it is
4,3,7,2,9,1,5
and H(3)=7 H(6)=1 H(7) = 5 so we have to rearrange to make the property true...
4,3,5,2,9,1,7
And since H(3) changed we have to check whether H(2) <= H(1) <=H(3) which it is
4,3,5,2,9,1,7,8,6
H(8) is not less than or equal to H(4) and H(4) less than or equal to H(9) so we rearrange:
4,3,5,6,9,1,7,2,8
Now H(2) is not between H(4) and H(5) so we rearrange:
4,6,5,3,9,1,7,2,8
And now H(1) is not between H(2) and H(3) so again rearrange:
5,4,6,3,9,1,7,2,8

Graphically it looks like this:

Now the median heap is built... notice that position n is greater than or equal to position 2*n
and less than position 2*n+1, it happens that the first number is the median and the left branches are less than the right branches, but this won't always be the case. So a second step can make it so that that is the case which may break the median heap property but is nicer for sorting, say...
It's possible to recurse the two steps on the two new half lists to eventually get a completely ordered list...

**Example**
The following is the output from the source code below for n=15, in general the list has to have an odd number of items for this code to run
input:
[86 57 24 16 53 91 2 87 83 58 22 89 91 89 33]
output:
[58 53 89 24 86 57 89 16 87 22 83 2 91 33 91]
See the root is the median of the set of numbers and all the odd positions are less than the even positions... Note that this does not have the median heap property because n=5 is 86 which is not between n=10 22 and n=11 83 because the second step broke the median heap property to make it so the root became the median and all even positions are less than the odd positions... I'll mark the spot where the second step begins in the code with a comment...

**Go source code**
```package main

import (
"fmt"
"math/rand"
"time"
)
func t(a int, b int, c int) (int, int, int, bool){
if (b <= a && a <= c){
return a,b,c, false
}
if (c <= a && a <=b){
return a,c,b, true
}
if (a <= b && b <= c){
return b,a,c, true
}
if (c <=b && b <= a){
return b,c,a, true
}
if (a <= c && c <= b){
return c,a,b, true
}
return c,b,a, true
}
func hc(h [] int, o int) ([] int){
f := true
for f == true{
a ,b ,c, f2 := t(h[o],h[2*o+1], h[2*o+2])
f = f2
h[o] = a
h[2*o+1] = b
h[2*o+2] = c
o = int(o/2.0)
}
return h
}
func main() {
l := make([] int, 15)
h := make([] int, 15)
rand.Seed(time.Now().UnixNano())

for i:=0; i<15; i++{
l[i] = rand.Intn(100)
}
fmt.Println(l)```
```    h[0] = l[0]
for i:=0; i<int(len(l)/2.0); i++{
h[2*i+1] = l[2*i+1]
h[2*i+2] = l[2*i+2]
h = hc(h, i)
}
//Second step breaking median heap property begins
for i:=1; i< len(h); i+=2{
f :=false
h[0], h[i], h[i+1], f = t(h[0], h[i], h[i+1])
if f == true{
i =1
}
}
fmt.Println(h)
```
}