Сортировка очереди. [c++]

[Jigarkhwar]

Общая задача. Имеется самая простая обыкновенная очередь(с одной головой), и её нужно с помощью heapSort отсортировать. У меня имеется код АТД очередь но суть вопроса пока что не в самом коде, а в логике. Чтобы отсортировать очередь нужно просеять элемент через неё. В общем вопрос как просеять элемент через очередь. Грубо говоря составить в этой очереди бинарное дерево. Чтобы отсеять сомнения - я прекрасно понимаю что внутри самой очереди это сделать нельзя. Следовательно нужны другие методы, там перестановки в несколько очередей как внешние карманы или работа с адресами. есть предложения какие ?

[Stilet]

я прекрасно понимаю что внутри самой очереди это сделать нельзя.

Тоесть? Очередь в твоем понимании список? Тогда сортировка пузырьком (как и любай другая) подойдет.

[Jigarkhwar]

Сообщение от Stilet

Тоесть? Очередь в твоем понимании список? Тогда сортировка пузырьком (как и любай другая) подойдет.

Очередь - линейный связанный список с принципом FIFO. А по поводу сортировки - нужно именно пирамидальной примерно за время O(n*log n)

[Stilet]

нужно именно пирамидальной

А-а-а если задача так поставлена...

[Jigarkhwar]

ну впринципе какая разница какая сортировка. Проблема заключается в том, как вытащить данные и обработать их грубо говоря как массивные. (но очередь построена на указателях). Допустим у нас 10 элементов. как вытащить i-ый элемент 2i и 2i+1 и куда деть остальные данные. Потом если нужно поменять местами их и составить последовательность с этими же данным и послать её опять в очередь.
1) 2 3 5 1 10 6 9 4 7 8
2) выбираем элементы 3 5 1
3) 3(родитель) меняем местами с большим сыном - 5
4) выстраиваем новую последовательность 2 5 3 1 10 6 9 4 7 8
что то вроде этого

[Stilet]

как вытащить данные

А как ты их вытаскиваешь? У тебя же есть голова - от нее и иди в цикле до конца очереди.

[Jigarkhwar]

а по какому параметру цикл то запускать ? в масивах по индексам а в указателях как ? или добавить инкремент при добавлении в очередь ?

[Stilet]

а по какому параметру цикл то запускать ?

А ты посмотри примеры вывода на экран списков. Цикл начинается с указателя на голову. Потом этому указателю присваивается следующий, значение которого содержится в элементе.
Поройся по форуму в поисках тем про динамические списки.
Вот например здесь: http://www.programmersforum.ru/showt...279#post713279
Пример проходя по списку в виде функции printlist()

P.S. Я надеюсь что под словом "очередь " имелась ввиду списочная структура а не просто динмассив?

[Jigarkhwar]

Сообщение от Stilet

P.S. Я надеюсь что под словом "очередь " имелась ввиду списочная структура а не просто динмассив?

Да, Верно.