堆排序算法

/**n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
　*(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)
  */

using System;
using System.Collections.Generic;
using System.Text;

namespace heapSortAlgorithm
{
    public class Node
    {
        public int data;
        public Node(int key)
        {
            data = key;
        }
    }

    class Heap
    {
        //const int maxSize = 10;
        //int currSize;
        //Node[] heapArray = new Node[maxSize];
        public void ShiftUp(int index)
        {
            int parent = (index - 1) / 2;
            Node bottom = heapArray[index];
            while ((index > 0) && (heapArray[parent].data < bottom.data))
            {
                heapArray[index] = heapArray[parent];
                index = parent;
                parent = (parent - 1) / 2;
            }
            heapArray[index] = bottom;
        }

        public bool Insert(int key)
        {
            if (currSize == maxSize)
                return false;
            heapArray[currSize] = new Node(key);
            ShiftUp(currSize);//This sentence is not existed in the original segment.
            currSize++;
            return true;
        }

        public Node Remove()
        {
            Node root = heapArray[0];
            currSize--;
            heapArray[0] = heapArray[currSize];
            ShiftDown(0);
            return root;
        }

        public void ShiftDown(int index)
        {
            int largerChild;
            Node top = heapArray[index];
            while (index < (int)(currSize / 2))
            {
                int leftChild = 2 * index + 1;
                int rightChild = leftChild + 1;
                if ((rightChild < currSize) && heapArray[leftChild].data < heapArray[rightChild].data)
                    largerChild = rightChild;
                else
                    largerChild = leftChild;
                if (top.data >= heapArray[largerChild].data)
                    break;
                heapArray[index] = heapArray[largerChild];
                index = largerChild;
            }
            heapArray[index] = top;
        }

        Node[] heapArray = null;
        private int maxSize = 0;
        private int currSize = 0;
        public Heap(int maxSize)
        {
            this.maxSize = maxSize;
            heapArray = new Node[maxSize];
        }
        public bool InsertAt(int pos, Node nd)
        {
            heapArray[pos] = nd;
            return true;
        }
        public void ShowArray()
        {
            for (int i = 0; i < maxSize; i++)
            {
                if (heapArray[i] != null)
                    System.Console.Write(heapArray[i].data + "  ");
            }
        }
        static void Main()
        {
            const int SIZE = 9;
            Heap aHeap = new Heap(SIZE);
            Random RandomClass = new Random();
            for (int i = 0; i < SIZE; i++)
            {

                int rn = RandomClass.Next(1, 100);
                aHeap.Insert(rn);
            }
            Console.Write("Random: ");
            aHeap.ShowArray();
            Console.WriteLine();
            Console.Write("Heap: ");
            for (int i = (int)SIZE / 2 - 1; i >= 0; i--)
                aHeap.ShiftDown(i);
            aHeap.ShowArray();
            for (int i = SIZE - 1; i >= 0; i--)
            {
                Node bigNode = aHeap.Remove();
                aHeap.InsertAt(i, bigNode);
            }
            Console.WriteLine();
            Console.Write("Sorted: ");
            aHeap.ShowArray();

            Console.ReadKey();
        }
    }

}