Найдите более эффективную сортировку кучи? - PullRequest
Новая
       23

Найдите более эффективную сортировку кучи?

0 голосов
/ 08 мая 2020

Мне нужно сделать мою сортировку кучи более эффективной, написав метод, который будет строить кучу на месте, используя массив для сортировки. Реализуйте такой метод и перепишите алгоритм сортировки кучи, чтобы использовать его.

Вот сортировка кучи 

public class HeapSort<T>
{

    public void heapSort(T[] data) 
    {
        ArrayHeap<T> heap = new ArrayHeap<T>();

        for (int i = 0; i < data.length; i++)
            heap.addElement(data[i]);

        int count = 0;
        while (!(heap.isEmpty()))
        {
            data[count] = heap.removeMin();
            count++;
        }
    }
}

Вот ArrayHeap Здесь реализована куча массива, но Я не знаю, где добавить новый метод 


public class ArrayHeap<T> extends ArrayBinaryTree<T> implements HeapADT<T> 
{

    public ArrayHeap() 
    {
        super();
    }


    public void addElement(T obj) 
    {
        if (count == tree.length)
            expandCapacity();

        tree[count] = obj;
        count++;
        modCount++;

        if (count > 1)
            heapifyAdd();
    }


    private void heapifyAdd()
    {
        T temp;
        int next = count - 1;

        temp = tree[next];

        while ((next != 0) && 
                (((Comparable<T>)temp).compareTo(tree[(next - 1) / 2]) < 0))
        {

            tree[next] = tree[(next - 1) / 2];
            next = (next - 1) / 2;
        }

        tree[next] = temp;
    }


    public T removeMin() throws EmptyCollectionException 
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        T minElement = tree[0];
        tree[0] = tree[count - 1];
        heapifyRemove();
        count--;
        modCount--;

        return minElement;
    }


    private void heapifyRemove()
    {
        T temp;
        int node = 0;
        int left = 1;
        int right = 2;
        int next;

        if ((tree[left] == null) && (tree[right] == null))
            next = count;
        else if (tree[right] == null)
            next = left;
        else if (((Comparable<T>)tree[left]).compareTo(tree[right]) < 0)
            next = left;
        else
            next = right;
        temp = tree[node];

        while ((next < count) && 
                (((Comparable<T>)tree[next]).compareTo(temp) < 0))
        {
            tree[node] = tree[next];
            node = next;
            left = 2 * node + 1;
            right = 2 * (node + 1);
            if ((tree[left] == null) && (tree[right] == null))
                next = count;
            else if (tree[right] == null)
                next = left;
            else if (((Comparable<T>)tree[left]).compareTo(tree[right]) < 0)
                next = left;
            else
                next = right;
        }
        tree[node] = temp;
    }


    public T findMin() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        return tree[0];
    }
}
...