4877

Пирамидальная сортировка и способы ее построения в программировании

Лекция

Информатика, кибернетика и программирование

Пирамидальная сортировка. Пирамидальная сортировка (heap sort) основывается на организации элементов в массиве по типу двоичного (бинарного) дерева. Двоичным деревом называют иерархическую структуру данных, в которой каждый элемент имеет не более дв...

Русский

2012-11-28

73.5 KB

44 чел.

Пирамидальная сортировка.

Пирамидальная сортировка (heap sort) основывается на организации элементов в массиве по типу двоичного (бинарного) дерева. Двоичным деревом называют иерархическую структуру данных, в которой каждый элемент имеет не более двух потомков:

Рис 1. Пример бинарного дерева.

Пирамида представляет собой особый вид бинарного дерева, в котором значение каждого элемента больше, чем значение каждого из его потомков. Непосредственные потомки каждого узла не упорядочены, поэтому иногда левый потомок может оказаться больше правого, а иногда – наоборот. Пирамида представляет собой полное дерево, в котором заполнение нового уровня начинается только после того, как предыдущий уровень полностью заполнен, а все узлы на одном уровне заполняются последовательно:

Рис 2. Пример пирамиды.

Сортировка начинается с построения пирамиды, содержащей все элементы исходной последовательности. Ясно, что максимальный элемент окажется в вершине дерева, поскольку все её потомки обязательно должны быть меньше. Затем, вершина пирамиды записывется в конец последовательности, а пирамида с удаленным максимальным элементом переформировывается. В результате, на её вершине оказывается максимальный из оставшихся элементов, он записывается на соответствующее место, и процедура продолжается до тех пор, пока пирамида не опустеет.

Таким образом, основную нагрузку алгоритма несут две процедуры: начальное построение пирамиды и переформирование пирамиды на каждом шаге. Для построения пирамиды можно воспользоваться её свойством – у каждого внутреннего узла ровно два непосредственных потомка, за исключением, быть может, одного узла на предпоследнем уровне. Следовательно, можно пронумеровать узлы, начиная с вершины по правилу: если узел имеет номер i, то его потомкам назначим номера 2*i и 2*i+1. В результате все узлы пирамиды получат уникальные номера в диапазоне 1 ~ N, что дает возможность хранить пирамиду в виде последовательности:

Рис 3. Списочное представление пирамиды (см рис.2).

При удалении наибольшего элемента пирамиды из вершины, корневой узел остается свободным. После перестроения пирамиды в него должен попасть больший из двух непосредственных потомков, в свою очередь аналогично нужно определить, кто встанет на его место и т.д. При этом пирамида должна оставаться настолько близкой к полному дереву, насколько возможно. С этой целью переформирование пирамиды будем начинать с крайнего правого элемента на нижнем уровне, перенося его на вершину. Затем к вершине применим процедуру, называемую «просеиванием вниз»:

  1.  если элемент не имеет потомков, то конец;
  2.  иначе меняем местами значения элемента и максимального из двух его непосредственных потомков;
  3.  переходим к изменившемуся потомку и выполняем для него ту же процедуру с шага 1.

Такой подход к перестроению пирамиды можно использовать также и для построения её начального состояния: любые два элемента можно считать потомками некоторого свободного узла. Поскольку все элементы являются «листьями», со второй половиной последовательности можно ничего не делать. Начиная с набора листовых элементов, можно соединять их попарно до тех пор, пока не будет сформирована общая большая пирамида. Первый добавляемый корень в последовательности из N элементов будет иметь индекс N / 2 - 1. В итоге алгоритм начального построения пирамиды будет заключаться в последовательном применении процедур «просеивания вниз» ко всем элементам с индексами от N / 2 - 1 до 0.

Рис. 4. Пример применения процедуры «просеивания вниз»

к измененному корневому элементу пирамиды.

// Функция "просеивает" элемент номер i вниз в пирамиде heap размера size

void fixHeap( double * heap, int i, const int size )

{   

   // Индекс максимального элемента в текущей тройке элементов:

   int maxIdx = i ;

   // Значение текущего элемента:

   double value = heap[i];

     

   while ( true )

   {

      int childIdx = i * 2 + 1; //Индекс левого потомка

      

      // Если есть левый потомок и он больше текущего элемента,

      if ( ( childIdx < size ) && ( heap[ childIdx ] > value ) )

         maxIdx = childIdx; //  то он считается максимальным

           

       childIdx = i * 2 + 2; //Индекс правого потомка

       

       // Если есть правый потомок и он больше максимального,

       if ( ( childIdx < size ) && ( heap[ childIdx ] > heap[ maxIdx ] ) )

           maxIdx = childIdx; //  то он считается максимальным

       // Если текущий элемент является максимальным из трёх

       // (т.е. если он больше своих детей), то конец:

       if ( maxIdx == i )

          break;

       

       // Меняем местами текущий элемент с максимальным:

       heap[i] = heap[ maxIdx ];

       heap[ maxIdx ] = value;

       

       // Переходим к изменившемуся потомку

       i = maxIdx;

   }

}

// Пирамидальная сортировка массива heap размера size

void heapSort( double * heap, int size )

{   

   // Построение пирамиды из массива:

   for( int i = size / 2 - 1; i >= 0; --i )

      fixHeap( heap, i, size );

   

   // Сортировка с помощью пирамиды

   while( size > 1 ) // пока в пирамиде больше одного элемента

   {

       --size; // Отделяем последний элемент

       // Обмениваем местами корневой элемент и отделённый:

       double firstElem = heap[0];

       heap[0] = heap[ size ];

       heap[ size ] = firstElem;

       

       // "Просеиваем" новый корневой элемент вниз:

       fixHeap( heap, 0, size );

   }

}


A

B

C

E

D

G

H

12

10

5

9

7

3

1

2

11

8

6

4

12

1

10

2

11

3

5

4

9

5

8

6

6

7

1

8

2

9

7

10

3

11

4

12

6

10

5

9

7

3

1

2

11

8

6

4

11

10

5

9

7

3

1

2

6

8

6

4

11

10

5

9

7

3

1

2

8

6

6

4


 

А также другие работы, которые могут Вас заинтересовать

44704. Структурирование Документа 407.5 KB
  Если таблицы или разделы не используются то каждый элемент размещения будет направлен в страницу или страницы на отдельных строках используя единственный столбец. Для каждой страницы или группы страниц один или более Разделов могут быть созданы. Для каждого Раздела ориентация на бумаге размер страницы края страницы страница опций номерования и номер столбцов может быть выбрана.
44705. Особенности библиотеки (Library Features) 2.13 MB
  Создание Библиотеки Шрифта Creting Font Librry Особенность текста входящая в РМ использует сделанные образцы шрифта. Они специализированы в схемы библиотек куда каждый символ номер символ шрифта нарисованный в одной ячейке библиотеки. Название ячейки для каждой ячейки образца шрифта фактический символ шрифта который ячейка представляет. Рисуйте все символы числа символы для вашего шрифта.
44706. Панели инструментов Pattern Makera 853 KB
  Панель Min Главная 1 создать новый файл схемы 2 импорт графического файла в новый файл схемы 3 открыть файл схемы 4 сохранить текущий файл 5 печать 6 вырезать выделенный фрагмент в буфер обмена 7 копировать выделенный фрагмент в буфер обмена 8 вставить фрагмент из буфера обмена на текущую схему 9 отменить действие 10 вставить схему из галереи 11 вызвать справку Панель View Вид 1 отобразить схему в виде крестиков 2 отобразить схему в виде символов 3 отобразить схему в виде цветных квадратов 4 показать...
44707. Работа программы PM для вышивки крестом 2.61 MB
  Основные Особенности РМ позволяет Вам создавать схемы которые включают следующий стежок напечатает: Полный крест Полукрест Четверть Миниатюрный Назад Прямо бэкстич Специальный Французский Узел Цепочка ячеек До 240 цветов мулине вышивального шелка может использоваться при содействии дизайна. Эта особенность удобна когда Вы хотите использовать нарисованный эскиз как схему {руководство} для вашего дизайна. После создания дизайна РМ позволяет Вам создавать размещение страницы для...
44708. Преобразование сканированной Фотографии 3.65 MB
  Чтобы открыть Мастера Импортирования выберите Import Imge и затем Импортируйте В Новую схему из меню File или щелкните кнопкой панели Import Imge. Чтобы развернуть экран щелкните кнопкой Mximum которая расположена в верхнем правом угле главного окна Pttern Mker. Щелкните Browse чтобы выбрать файл. Щелкните Open после вашего выбора.
44709. Использование Обеспеченного Графического элемента 2.46 MB
  Выберите New от меню File. Выберите Sve от меню File чтобы сохранить ваш дизайн. Выберите Copy в Библиотеке в меню Librry или щелкните соответствующей кнопкой панели. Выберите Sve от меню File чтобы сохранить ваш дизайн.
44710. Особенности Стежка 508 KB
  Выберите цвет мулине который используется для стежка. Нажмите на инструмент Полный Миниатюрный Половина или стежка Четверти Панели рисования: 3. Чтобы использовать только первую нарисованную ориентацию стежка выберите Repet First Stitch Orienttion в меню Stitch.
44711. Диалог Вариантов стежка 510 KB
  Фактическая Толщина Страница Фактической толщины диалогового окна Stitch Options позволяет Вам определять заданную по умолчанию толщину для каждого типа стежка. Определите заданную по умолчанию толщину стежка для каждого типа стежка. Толщина Дисплея Страница Толщины Дисплея диалогового окна Stitch Options позволяет Вам определять дисплей и напечатанную толщину для каждой возможной толщины стежка.
44712. Сужение Выбора Цвета и Типа Стежка 1.3 MB
  Установите указатель в пределах выбора и затем щелкните и удержите левую кнопку мыши. Они: Точечный рисунок – Эта опция копирует растровое представление выбора в буфер обмена. Используйте инструмент выбора чтобы сделать выбор.