4877

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

Лекция

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

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

Русский

2012-11-28

73.5 KB

46 чел.

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

Пирамидальная сортировка (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


 

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

82036. Техническое обслуживание и ремонт сцепления КамАЗ-4310 490.5 KB
  Автомобильный транспорт является наиболее массовым и удобным видом транспорта, обладающим большой маневренностью хорошей проходимостью и приспособленностью для эксплуатации в разных климатических и географических условиях.
82037. Технология изготовления детали подшипника на автоматизированном оборудовании с ПУ 5.4 MB
  Оборудование с ЧПУ может быть представлено: станочным парком например станками станки оборудованные числовым программным управлением называются станками с ЧПУ: для обработки металлов например фрезерные или токарные дерева пластмасс для резки листовых заготовок для обработки давлением и т.
82038. Проектування магістральної волоконно-оптичної лінії зв’язку між м. Луцьк та м. Хмельницький 1.59 MB
  Розвиток засобів зв’язку має велике значення для ефективного керування народним господарством чіткої роботи державного апарату та всебічного задоволення населення в потребі зв’язку і технічних засобів інформації. А це потребує збільшення пропускної спроможності лінії зв’язку приблизно в 10 разів кожні 1617 років.
82039. Разработка рекламного продукта для декоративного покрытия «Модесто» 18.14 MB
  Характеристики рекламируемого товара. На основе информации собранной из различных источников составляется перечень основных характеристик товара. В качестве основных характеристик которые желательно иметь для разработки рекламного продукта можно выделить следующие: наименование товара...
82040. Основные компоненты бизнес-плана Агентства наружной рекламы 464.5 KB
  Обычно полотно перетяжки изготавливается методом трафаретной печати на хлопчатобумажной ткани. При необходимости размещения на длительный срок или при изготовлении сложного макета используется либо сублимационная печать на шелковой ткани, либо печать на баннере.
82041. Тиристорні перетворювачі 297.5 KB
  Система імпульснофазового управління в свою чергу складається із вузла що перетворює напругу управління в послідовність імпульсів визначеної тривалості форми моменти яких залежать від напруги управління; вузла підсилення імпульсів що формує імпульси з визначеними електричними параметрами.
82042. Туристическая база 13.36 MB
  Туризм можно классифицировать по различным критериям: По цели отдыха По характеру отдыха и его организации По продолжительности путешествия По сезонности Эти критерии имеют решающее значение потому что именно цель поездки больше всего влияет на формирование тура и организацию туристического обслуживания.
82043. Изготовление изделий из бисера 6.73 MB
  В настоящее время бисерная вышивка переживает свой расцвет. Это красиво, модно, современно. Вышивкой из бисера украшают не только платья, кофточки, но и обувь, сумки и многое другое. Основой для вышивки служат холст, лен, бархат, атлас, шерсть. Сукно. Нитки следует брать армированные, чтобы бусинки их не перетирали.
82044. Країни південно-східної Азії у другій половині ХХ-го століття 7.55 MB
  Економічна колонізація Вєтнаму французьким капіталом розпочата у другій половині ХІХ ст. в умовах післявоєнного економічного буму французькі колонізатори вдалися до розширеної експлуатації людських і природних багатств Вєтнаму.