读书笔记 算法导论 堆排序

感觉自己算法不给力额...对基本概念和基本操作都不够熟悉

准备吧整个算法导论过一遍...把大部分常用的东西自己写一遍

做it真是辛苦啊...

先弄个常用的堆吧

堆可以用作堆排序,优先队列等等情况

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

namespace IntroduceToAlgorithm
{

    public class MaxHeap
    {
        /// <summary>
        /// check the node is obey Max_Heap_property or not
        /// </summary>
        /// <param name="A">an int array represent a heap</param>
        /// <param name="i">the node index</param>
        /// <param name="aLength">the arry length , (some time, we will reduce the length of array)</param>
        public void MaxHeapify(int[] A, int i, int aLength = -1)
        {
            int length = aLength <= -1 ? A.Length : aLength;
            
            var l = Left(i);
            var r = Right(i);
            int largest = i;

            if (l < length && A[l] > A[i])
            {
                largest = l;
            }

            if (r < length && A[r] > A[largest])
            {
                largest = r;
            }

            if (largest != i)
            {
                Exchange(A, i, largest);
                MaxHeapify(A, largest, aLength);
            }
            //MaxHeapify(A, l);
            //MaxHeapify(A, i);


        }

        public int Left(int index)
        {
            return (index + 1) * 2 - 1;
        }

        public int Right(int index)
        {
            return (index + 1) * 2;
        }

        public void Exchange(int[] A, int i, int i2)
        {
            int val = A[i];
            A[i] = A[i2];
            A[i2] = val;
        }

        /// <summary>
        /// build a max-heap, all element obey max-heap-property
        /// wo only need check element which index less than A.Length/2 -1 
        /// </summary>
        /// <param name="A"></param>
        public void Build_Max_Heap(int[] A)
        {
            for (int i = (A.Length / 2 - 1); i >= 0; i--)
            {
                MaxHeapify(A, i);
            }

        }

        public void HeapSort(int[] A)
        {
            int length = A.Length;
            Build_Max_Heap(A);
            for (int i = A.Length - 1; i >= 1; i--)
            {
                Exchange(A, 0, i);
                MaxHeapify(A, 0, --length);
            }
        }

    }

}

PS:看伪代码有的时候很郁闷 例如C#数组下标开始是0,伪代码中一般是1  转换来转换去就乱了.......尴尬