Sunday, November 1, 2015

median heaps and a sorting method

Suppose you have a list of some sortable items indexed naturally starting at 1:
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:

Start with the first three items:
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:
Now the property is satisfied so we add two more numbers from the list
H(2) =2 H(4)=9 H(5)=3 so we have to rearrange those three numbers to satisfy the property
Now since H(2) changed we have to again see whether H(2)<= H(1) <=H(3) which it is
so add another two numbers
and H(3)=7 H(6)=1 H(7) = 5 so we have to rearrange to make the property true...
And since H(3) changed we have to check whether H(2) <= H(1) <=H(3) which it is
so we add two more
H(8) is not less than or equal to H(4) and H(4) less than or equal to H(9) so we rearrange:
Now H(2) is not between H(4) and H(5) so we rearrange:
And now H(1) is not between H(2) and H(3) so again rearrange:

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...

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
[86 57 24 16 53 91 2 87 83 58 22 89 91 89 33]
[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 (
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)
    for i:=0; i<15; i++{
        l[i] = rand.Intn(100)
    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

No comments:

Post a Comment