鸟语天空

堆排序(二)

作者：追风剑情 发布于：2016-6-20 13:17 分类：Algorithms

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

namespace HeapSortTest
{
    class Program
    {
        static void Main(string[] args)
        {
            //测试数据, 有效值从R[1]开始
            List<int> R = new List<int>() { 0, 75, 87, 68, 92, 88, 61, 77, 96, 80, 72 };
            Console.Write("测试数据： ");

            //创建一个有序堆对象，并添加测试数据。
            HeapSort heap = new HeapSort();
            for (int i = 1; i < R.Count; i++)
            {
                Console.Write(R[i] + " ");
                heap.Push(R[i]);
            }

            Console.WriteLine();

            Console.Write("依次移除堆中数据: " );
            int r1;
            while((r1 = heap.Shift()) != -1){
                Console.Write(r1 + " ");
            }

            Console.Read();
        }
    }

    /// <summary>
    /// 有序堆
    /// </summary>
    public class HeapSort
    {
        List<int> R;

        public HeapSort()
        {
            R = new List<int>();
            //堆排序不会用到0号元素，这里设个占位符。
            R.Add(-1);
        }

        //筛选方法
        private void SiftLess(List<int> R, int low, int high)
        {
            int i = low, j = 2 * i;
            int tmp = R[i];
            while (j <= high)
            {
                if (j < high && R[j] > R[j + 1])
                {
                    j++;
                }
                if (tmp > R[j])
                {
                    R[i] = R[j];
                    i = j;
                    j = 2 * i;
                }
                else
                {
                    break;
                }
            }
            R[i] = tmp;
        }

        //添加元素
        public void Push(int value)
        {
            R.Add(value);
            int high = R.Count - 1;
            int i = high / 2;//最后一个元素的父节点索引
            int j = high;//最后一个元素索引
            int tmp;

            while (i >= 1)
            {
                if (R[i] > R[j])
                {
                    tmp = R[i];
                    R[i] = R[j];
                    R[j] = tmp;
                    j = i;
                    i /= 2;
                }
                else
                {
                    break;
                }
            }
        }

        //移除根元素
        public int Shift()
        {
            int high = R.Count - 1;

            if (high <= 1)
                return -1;

            int r1;
            if (high <= 3)
            {
                r1 = R[1];
                R.RemoveAt(1);
                return r1;
            }

            r1 = R[1];
            R[1] = R[high];
            R.RemoveAt(high);
            SiftLess(R, 1, high - 1);

            return r1;
        }
    }
}

运行测试

标签: Algorithms