Heap Sort

What is a Heap?
- Consider the case of ascend sorting, Heap is defined as an array of element a_l , a_l+1 ...a_r that satisfy: ∀ i belong to [l,r] and i starts from 0
  

1/.	ai  >= a2i +1
2/.	ai  >= a2i+2     {(ai , a2i +1), (ai ,a2i+2) is a pair of joint elements}

-  If  a_l , a_l+1 ...ar is a Heap,  a_l is the largest element


Algorithm:
- Phase 1: Adjust the initial array to heap (from the middle element of the array)
- Phase 2: Sort the array base on heap

• Step 1: move the largest element to the end of the array
• Step 2:
  + Exclude the largest element out of heap: r = r-1 
  + Adjust the remain of array
• Step 3: Compare r and l:
  + If r > l, repeat step 2
  + Else: stop

Implementation:
        public static void HeapSort (double[] list)
        {
            CreateHeap(list);         
            for (int i = list.Length - 1; i >= 1; i--)
            {
                double Temp = list[0];
                list[0] = list[i];
                list[i] = Temp;              
                Shift (list, 0, i - 1);
            }           
        }
       
        private static void CreateHeap(double []a)
        {         
            for (int i = (a.Length - 1) / 2; i >= 0; i--)
                Shift(a, i, a.Length - 1);
        }

        static void Shift(double[] a, int left, int right)
        {
            int curr = left;
            int joint = 2 * curr + 1;
            double x = a[curr];

            while (joint <= right)
            {
                if (joint < right)
                { 
                    if (a[joint] < a[joint + 1])
                    {
                        joint = joint + 1;
                    }
                }
                if (a[joint] < x)
                {
                    break;
                }
                a[curr] = a[joint];
                curr = joint;
                joint = 2 * curr + 1;
            }
            a[curr] = x;
        }
         
Hope this help!

Posted in: Algorithm, Heap Sort, Sorting