heapsort

Hi,

ich vermisse das shift im heapsort...wo finde ich das...bzw kann man es etwas übersichtlicher coden?
- wo ist mein shift?

nehemen wir an ich habe das parent node an pos i:
- dann ist mein linkes child an pos 2i+1
- dann ist mein rechtes child an pos 2i+2
...wo sehe ich das?

class heapsort
{
	private:
		int *arr;
		int count;

	public:
		heapsort(int *a, int length)
		{
			arr = a;
			count = length;
		}

		void makeheap(int c)
		{
			for (int i = 1; i < c; i++)
			{
				int val = arr[i];
				int s = i;
				int f = (s - 1) / 2;

				while (s > 0 && arr[f] < val)
				{
					arr[s] = arr[f];
					s = f;
					f = (s - 1) / 2;
				}
				arr[s] = val;
			}
		}

		void sort()
		{
			for (int i = count - 1; i > 0; i--)
			{
				swap(arr[i], arr[0]);
				makeheap(i);
			}
		}
};

int main()
{
    int arr[] = {12, 2, 8, 13, 58, 26, 17, 1, 90, 3};

    heapsort hp(arr, sizeof(arr)/sizeof(int));
    hp.makeheap(sizeof(arr)/sizeof(int));
    hp.sort();
}

Thuruk

bzw kann man es etwas übersichtlicher coden?

void makeheap(int c)
        {
            for (int i = 1; i < c; ++i) //normales inc i, bei allen Schleifen
            {
                int s = i;
                int f = (s - 1) >> 1; //Division durch Rechtsshiften

                while (s > 0 && arr[f] < arr[i])
                {
                    arr[s] = arr[f];
                    s = f;
                    f = (s - 1) >> 1;
                }
                arr[s] = arr[i];
            }
        }

Und warum als Klasse? Funktion, die ein neues Array erzeugt, wäre besser.

wo sehe ich das meine childs wie folgt zugegriffen wird?

- linkes child an pos 2i+1
- rechtes child an pos 2i+2

Swordfish

Thuruk schrieb:

[...] Funktion, die ein neues Array erzeugt, wäre besser.

Wer gibt den Speicher frei?

wo sehe ich das meine childs wie folgt zugegriffen wird?

- linkes child an pos 2i+1
- rechtes child an pos 2i+2