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


 

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

65737. МОДЕЛЮВАННЯ І ПРОГНОЗУВАННЯ ДІЇ НЮХОВОГО НАНОБІОСЕНСОРА НА ОСНОВІ МОЛЕКУЛИ БІЛКА ТИПУ GPCR 481.5 KB
  Причинами цього є поперше те що сучасна кремнієва електроніка досягає межі мініатюризації і для виведення її на якісно новий рівень розвитку створення так званого квантового комп'ютера необхідна нова фізична елементна база з елементами розміру порядку нанометра тобто розміру молекули.
65738. Робота та розрахунок сталевих нагельних з’єднань дерев’яних конструкцій за повторних навантажень 1.33 MB
  Велике значення мають дослідження міцнісних і деформативних характеристик нагельних з'єднань дерев'яних елементів при одноразових та повторних навантаженнях оскільки при експлуатації значна кількість дерев'яних конструкцій знаходяться саме в таких умовах.
65739. ПРАВОВЕ РЕГУЛЮВАННЯ ПРОТИДІЇ ІНФОРМАЦІЙНИМ ВІЙНАМ В УКРАЇНІ 155.5 KB
  Незважаючи на надзвичайну важливість забезпечення належного функціонування всіх сфер життєдіяльності людини суспільства та держави необхідність ефективного забезпечення інформаційної безпеки держави зокрема шляхом вироблення надійного механізму протидії інформаційним війнам...
65740. СТАН АНТИОКСИДАНТНОЇ СИСТЕМИ ТА НЕСПЕЦИФІЧНА РЕЗИСТЕНТНІСТЬ У ТВАРИН ЗА ДІЇ ПРОБІОТИКІВ БПС 44 ТА БПС Л 227.5 KB
  Мета роботи: зясувати вплив пробіотичних препаратів БПС44 та БПСЛ на стан антиоксидантної системи та неспецифічну резистентність молодняку великої рогатої худоби ВРХ та свиней; встановити фактори антагоністичної дії штамів бактерій компонентів пробіотиків.
65741. ЗАБЕЗПЕЧЕННЯ ЯКОСТІ ПОСЛУГ ПЕРЕДАЧІ МУЛЬТИМЕДІА МЕРЕЖАМИ НОВОГО ПОКОЛІННЯ 1.25 MB
  Даний процес може сприяти виникненню проблем які повязані із гарантуванням рівня якості обслуговування мереж передачі мультимедійної інформації. Передплатники цих систем передачі мультимедійної інформації вимагають надання нових послуг які можуть бути доступними в будь якому місці...
65742. КІНЕМАТИЧНІ ПАРАМЕТРИ ГАЛАКТИКИ ЗА ДАНИМИ СУЧАСНИХ АСТРОМЕТРИЧНИХ КАТАЛОГІВ 3.19 MB
  Оскільки масових визначень променевих швидкостей поки що недостатньо для детальних кінематичних досліджень Галактики власні рухи зір є єдиним численним джерелом даних для таких досліджень. При цьому як зазначалось ще Дю Монтом дуже важливо мати...
65743. РАННЯ ДIАГНОСТИКА ТА ПРОГНОЗУВАННЯ БРОНХОЛЕГЕНЕВОЇ ДИСПЛАЗІЇ У НЕДОНОШЕНИХ НОВОНАРОДЖЕНИХ 356.5 KB
  Упровадження сучасних технологій виходжування недоношених новонароджених високотехнологічних методик ШВЛ використання сурфактанту призвело до збільшення виживаності недоношених новонароджених що у свою чергу вплинуло на збільшення частоти БЛД. На сьогоднішній день існує безліч суперечок і питань у профілактиці та лікуванні БЛД.
65744. ПРАВОВІДНОСИНИ ІЗ ЗАГАЛЬНООБОВ’ЯЗКОВОГО ДЕРЖАВНОГО СОЦІАЛЬНОГО СТРАХУВАННЯ 161.5 KB
  Це право гарантується зокрема загальнообов'язковим державним соціальним страхуванням за рахунок страхових внесків громадян підприємств установ та організацій. Основ законодавства України про загальнообов'язкове державне соціальне страхування.
65745. ОСОБЛИВОСТІ ФОРМУВАННЯ ТЕРАПЕВТИЧНОГО АЛЬЯНСУ У МЕДИЧНОМУ ЗАКЛАДІ ПСИХОНЕВРОЛОГІЧНОГО ПРОФІЛЮ 236 KB
  У звязку з реформуванням системи охорони здоровя зміною характеру відносин між лікарем і пацієнтом упровадженням принципу партнерства у їх взаємодію значною мірою зростає увага до проблеми терапевтичного альянсу В. Проблематику терапевтичного альянсу розглянуто лише в поодиноких наукових...