Patience Sort реализация C#

Banged

Пытаюсь разобраться с алгоритмом терпеливой сортировки, вроде даже как разобрался с принципом работы алгоритма, но в некоторых случаях элементы не совсем правильно сортируются, думаю что ошибка в "сборке" ответа из стэков. Возможно, кто-то заметит в чем ошибка.

Вот моя реализация:

class PriorityQueue<t> where T : IComparable
{
    private List<stack<t>> piles;

    public PriorityQueue(List<stack<t>> piles)
    {
        this.piles = piles;
    }

    public void SiftDown(int i)
    {
        while (2 * i + 1 < piles.Count)
        {
            int left = 2 * i + 1;

            int right = 2 * i + 2;

            int j = left;

            if (right < piles.Count && piles[right].Peek().CompareTo(piles[left].Peek()) <= 0)
                j = right;

            if (piles[i].Peek().CompareTo(piles[j].Peek()) <= 0)
                break;

            Swap(piles, i, j);

            i = j;
        }
    }

    public T Min()
    {
        T min = piles[0].Pop();
        if (piles[0].Count == 0)
            piles.RemoveAt(0);
        else
            SiftDown(0);
        return min;
    }

    private static void Swap<titem>(List<titem> list, int i, int j)
    {
        var tmp = list[i];
        list[i] = list[j];
        list[j] = tmp;
    }

    public void BuildHeap()
    {
        for (int i = piles.Count / 2; i >= 0; i--)
            SiftDown(i);
    }

}

class PatienceSort<t> where T : IComparable
{
    public static List<stack<t>> Piles = new List<stack<t>>();


    public static void Sort(List<t> list)
    {
        Piles = new List<stack<t>>();
        for (int i = 0; i < list.Count; i++)
        {
            int j = BinarySearch(list[i]);

            if (j == Piles.Count)
            {
                Piles.Add(new Stack<t>());
                Piles[Piles.Count - 1].Push(list[i]);
            }
            else
                Piles[j].Push(list[i]);
        }

        PriorityQueue<t> priorityQueue = new PriorityQueue<t>(Piles);

        priorityQueue.BuildHeap();

        int count = 0;

        while (Piles.Count != 0)
            list[count++] = priorityQueue.Min();
    }

    private static int BinarySearch(T item)
    {
        int left = 0, rigth = Piles.Count - 1;
        while (left <= rigth)
        {
            int mid = (left + rigth) / 2;
            if (Piles[mid].Peek().CompareTo(item) >= 0)
                rigth = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }

}
</t></t></t></stack<t></t></stack<t></stack<t></t></titem></titem></stack<t></stack<t></t>

И результаты работы на случайных данных:

10 -90 -84 -63 -37 -29 5 47 64 98 93

20 -196 -196 -192 -178 -174 -164 -113 -110 -107 -79 -79 -41 -38 -30 -12 6 33 13 180 199

30 -277 -268 -229 -226 -220 -214 -212 -182 -122 -107 -157 -112 -104 -104 -90 -81 -73 -25 -51 -24 5 15 108 90 136 159 160 196 228 260

1 ответ

Banged

Проблема в функции Min. Замените её вот на что:

public T Min()
{
    T min = piles[0].Pop();
    if (piles[0].Count == 0)
    {
        if (piles.Count >= 1)
            Swap(piles, 0, piles.Count - 1);
        piles.RemoveAt(piles.Count - 1);
    }

    if (piles.Count > 1)
        SiftDown(0);
    return min;
}

Пояснение. Конструкция

if (piles[0].Count == 0)
    piles.RemoveAt(0);

в вашем коде неверна, т. к. если остались ещё другие наборы (то есть, piles.Count > 1), вы, удаляя нулевой элемент, нарушаете свойство двоичной кучи: индексы элементов кучи имеют значение, и сдвигать их нельзя!

Поэтому сделаем следующее: если у нас ещё есть другие наборы, мы не удаляем минимальный набор, а заменяем его на тот, который можно безопасно забрать из кучи — то есть, на последний. В этом случае нам необходимо тоже провести процедуру SiftDown(0), восстанавливающую минимальное свойство вершины кучи.

licensed under cc by-sa 3.0 with attribution.