4877

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

Лекция

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

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

Русский

2012-11-28

73.5 KB

47 чел.

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

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


 

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

81084. ЗЛОУПОТРЕБЛЕНИЕ СУБЪЕКТИВНЫМИ ГРАЖДАНСКИМИ ПРАВАМИ НА ПРИМЕРЕ КОРПОРАТИВНЫХ ПРАВООТНОШЕНИЙ 172.47 KB
  Актуальность темы дипломной работы обусловлена необходимостью решения одной из самых неоднозначных проблем гражданского права - злоупотребления правом на примере корпоративных правоотношений. Необходимо отметить, что правоприменительная практика сталкивается с большим количеством корпоративных...
81085. ФЕМИНИСТИЧЕСКАЯ ТЕОЛОГИЯ КОНЦА 20-ГО ВЕКА В ПОИСКАХ МЕТОДОЛОГИИ 266 KB
  В период раннего капитализма традиционная точка зрения на положение женщины в обществе подвергается пересмотру: впервые говорится о различии в общественной сфере занятости необходимости строгого разграничения частного и общественного.
81087. ПРИОРИЕТЫ БЮДЖЕТНО-НАЛОГОВОЙ ПОЛИТИКИ РФ 45.51 KB
  Полнота бюджета, как правило, прямо пропорциональна благосостоянию граждан. Бюджет, его формирование и статьи расходов являются важным разделом в экономической науки, требующим большого внимания со стороны не только занимающих высокие посты экономистов и политиков, но и рядовых граждан.
81088. Электронные выпрямители, преобразователи, защита электронных устройств и основные характеристики 468.06 KB
  Инвертор который формирует частоту напряжения электродвигателя. Преобразователи частоты различаются по режиму коммутации используемому для регулирования напряжения питания электродвигателя.
81089. СОЗДАНИЕ ГОСУДАРСТВЕННОГО СТАНДАРТА ISO 21500:2012 30.93 KB
  Задачей рабочей группы по созданию стандарта было взять за основу опыт существующих организаций по управлению проектами (Института управления проектами PMI (США), Британского института стандартизации BSI и Международной ассоциации управления проектами IPMA) и свести его в лучшую практику – универсальный стандарт.
81090. Изменения в системе государственного управления при правлении Ивана III 50 KB
  Иван III заложил основы российского самодержавства не только значительно расширив территорию своего государства но и укрепив его политический строй государственный аппарат резко возвысив международный престиж Москвы. Иван III явился фактическим создателем Московского государства.
81091. Разработки и построение моделей социальных процессов для определения сущности, областей применения и наиболее эффективных методов моделирования 23.61 KB
  Актуальность темы состоит в том что в настоящее время нельзя назвать область человеческой деятельности в которой в той или иной степени не использовались бы методы моделирования. Остановимся на философских аспектах моделирования а точнее общей теории моделирования. Методологическая основа моделирования.
81092. Манипуляции в деловом общении и способы их нейтрализации 30.02 KB
  Очень важны психологические аспекты делового общения. Вопрос, с которым постоянно сталкиваются деловые люди, как построить беседу, переговоры. Важно понимать общие закономерности делового общения, что позволит анализировать ситуацию, учитывать интересы партнера, говорить на общем языке.