algorithm
ढेर बनाएं और छांटें

हीप सॉर्ट बेसिक जानकारी

हीप सॉर्ट बाइनरी हीप डेटा संरचना पर एक तुलना आधारित सॉर्टिंग तकनीक है। यह चयन प्रकार के समान है जिसमें हम पहले अधिकतम तत्व को ढूंढते हैं और इसे डेटा संरचना के अंत में डालते हैं। फिर शेष वस्तुओं के लिए भी यही प्रक्रिया दोहराएं।

छंद के लिए छद्म कोड:

function heapsort(input, count)
    heapify(a,count)
    end <- count - 1
    while end -> 0 do
    swap(a[end],a[0])
    end<-end-1
    restore(a, 0, end)

function heapify(a, count)
    start <- parent(count - 1)
    while start >= 0 do
        restore(a, start, count - 1)
        start <- start - 1

हीप सॉर्ट का उदाहरण:

सहायक स्थान: O(1)
समय जटिलता: O(nlogn)

C # कार्यान्वयन

public class HeapSort
{
    public static void Heapify(int[] input, int n, int i)
    {
        int largest = i;
        int l = i + 1;
        int r = i + 2;

        if (l < n && input[l] > input[largest])
            largest = l;

        if (r < n && input[r] > input[largest])
            largest = r;

        if (largest != i)
        {
            var temp = input[i];
            input[i] = input[largest];
            input[largest] = temp;
            Heapify(input, n, largest);
        }
    }

    public static void SortHeap(int[] input, int n)
    {
        for (var i = n - 1; i >= 0; i--)
        {
            Heapify(input, n, i);
        }
        for (int j = n - 1; j >= 0; j--)
        {
            var temp = input[0];
            input[0] = input[j];
            input[j] = temp;
            Heapify(input, j, 0);
        }
    }

    public static int[] Main(int[] input)
    {
        SortHeap(input, input.Length);
        return input;
    }
}