C#算法基础之堆排序

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace ConsolePractice
  8 {
  9     public class Node
 10     {
 11         public int data;
 12         public Node(int key)
 13         {
 14             data = key;
 15         }
 16     }
 17 
 18     class Heap
 19     {
 20         Node[] heapArray = null;
 21         private int maxSize = 0;
 22         private int currSize = 0;
 23         public Heap(int maxSize)
 24         {
 25             this.maxSize = maxSize;
 26             heapArray = new Node[maxSize];
 27         }
 28 
 29         public bool InsertAt(int pos, Node nd)
 30         {
 31             heapArray[pos] = nd;
 32             return true;
 33         }
 34 
 35         public void ShowArray()
 36         {
 37             for (int i = 0; i < maxSize; i++)
 38             {
 39                 if (heapArray[i] != null)
 40                     Console.Write(heapArray[i].data + " ");
 41             }
 42             Console.WriteLine();
 43         }
 44 
 45         public void ShiftUp(int index)
 46         {
 47             int parent = (index - 1) / 2;
 48             Node bottom = heapArray[index];
 49             while ((index > 0) && (heapArray[parent].data < bottom.data))
 50             {
 51                 heapArray[index] = heapArray[parent];
 52                 index = parent;
 53                 parent = (parent - 1) / 2;
 54             }
 55             heapArray[index] = bottom;
 56         }
 57 
 58         public bool Insert(int key)
 59         {
 60             if (currSize == maxSize)
 61                 return false;
 62             heapArray[currSize] = new Node(key);
 63             currSize++;
 64             return true;
 65         }
 66 
 67         public Node Remove()
 68         {
 69             Node root = heapArray[0];
 70             currSize--;
 71             heapArray[0] = heapArray[currSize];
 72             ShiftDown(0);
 73             return root;
 74         }
 75 
 76         public void ShiftDown(int index)
 77         {
 78             int largerChild;
 79             Node top = heapArray[index];
 80             while (index < (int)(currSize / 2))
 81             {
 82                 int leftChild = 2 * index + 1;
 83                 int rightChild = leftChild + 1;
 84                 if ((rightChild < currSize) && heapArray[leftChild].data < heapArray[rightChild].data)
 85                     largerChild = rightChild;
 86                 else
 87                     largerChild = leftChild;
 88                 if (top.data >= heapArray[largerChild].data)
 89                     break;
 90                 heapArray[index] = heapArray[largerChild];
 91                 index = largerChild;
 92             }
 93             heapArray[index] = top;
 94         }
 95     }
 96 
 97     class C_shape
 98     {
 99         static void Main()
100         {
101             const int SIZE = 9;
102             Heap aHeap = new Heap(SIZE);
103             Random RandomClass = new Random();
104             for (int i = 0; i < SIZE; i++)
105             {
106                 int rn = RandomClass.Next(1, 100);
107                 aHeap.Insert(rn);
108             }
109             
110             Console.WriteLine("Random:");
111             aHeap.ShowArray();
112             
113             Console.WriteLine("Heap:");
114             for (int i = (int)SIZE / 2 - 1; i >= 0; i--)
115             {
116                 aHeap.ShiftDown(i);
117             }
118             aHeap.ShowArray();
119 
120             Console.WriteLine("Sorted:");
121             for (int i = SIZE - 1; i >= 0; i--)
122             {
123                 Node bigNode = aHeap.Remove();
124                 aHeap.InsertAt(i, bigNode);
125             }
126             aHeap.ShowArray();
127             Console.ReadKey();
128         }
129     }
130 }