heapsort.cs

using System;

static class Heapsort{
    struct Node{
        public int[] List;
        public int Root_i;
        public int Bottom_i;
        public int Root{
            get{return this.List[this.Root_i];}
        }
        public int? Child1_i{
            get{ 
                if(this.Bottom_i < (this.Root_i + 1) * 2 - 1) return null;
                return (this.Root_i + 1) * 2 - 1;
            }
        }
        public int? Child1{
            get {
                if(this.Child1_i == null) return null;
                return this.List[(int)this.Child1_i];
            } 
        }

        public int? Child2_i{
            get{
                if (this.Bottom_i < (this.Root_i + 1) * 2) return null;
                return (this.Root_i + 1) * 2;
            }
        }

        public int? Child2{
            get {
                if (this.Child2_i == null) return null;
                return this.List[(int)this.Child2_i];
            }
        }

        public void ShiftDown(){
            if (this.Child1 == null) return;
            if (this.Child2 == null){
                if(this.Child1 < this.Root) return;
                this.List.Swap(this.Root_i, (int)this.Child1_i);
                this.Root_i = (int)this.Child1_i;
                this.ShiftDown();
                return;
            }
            if (this.Child1 < this.Root && this.Child2 < this.Root) return;
            if (this.Child1 < this.Child2){
                this.List.Swap(this.Root_i, (int)this.Child2_i);
                this.Root_i = (int)this.Child2_i;
                this.ShiftDown();
                return;
            } else {
                this.List.Swap(this.Root_i, (int)this.Child1_i);
                this.Root_i = (int)this.Child1_i;
                this.ShiftDown();
                return;
            }
        }
    }

    static int[] Sort(this int[] list){
        var node = new Node();
        node.List = list;

        for(var i = list.Length / 2; 0 < i; --i){
            node.Root_i = i - 1;
            node.Bottom_i = list.Length - 1;
            node.ShiftDown();
        }

        Console.WriteLine("");
        for(var i = list.Length - 1; 0 < i; --i){
            list.Swap(0, i);
            node.Root_i = 0;
            node.Bottom_i = i - 1;
            node.ShiftDown();
        }

        return list;
    }

    public static void Swap(ref int lh, ref int rh){
        var temp = lh;
        lh = rh;
        rh = temp;
    }

    public static void Swap(this int[] list,int index1, int index2){
        var temp = list[index1];
        list[index1] = list[index2];
        list[index2] = temp;
    }

    public static String ToPrintString(this int[] list){
        return "[" + String.Join(" ", list) + "]";
    } 

    static void Main(string[] args){
        var list = new int[]{3,0,1,8,7,2,5,4,9,6};
        Console.WriteLine("from:" + list.ToPrintString());
        Console.WriteLine("sort:" + list.Sort().ToPrintString());
    }
}