4877

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

Лекция

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

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

Русский

2012-11-28

73.5 KB

45 чел.

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

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


 

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

76720. Прилуки – мій рідний край 32.73 KB
  У 1993 році кількість населення становила 74,1 тис. осіб. В 1999 році населення міста вже становить 70,7 тис. осіб, починаючи з 1993 року, населення Прилук зменшується в результаті механічного і природного руху. Чисельність наявного населення міста станом на 1 жовтня 2005 року становила 61,6 тис. осіб.
76721. Средства массовой информации: информирование и предвыборная агитация (законодательные дозволения и запреты) 61.43 KB
  Цель исследования состоит в том, чтобы на основе имеющихся нормативно-правовых и теоретических источников, проанализировать процесс становления конституционно-правового регулирования предвыборной агитации и ее финансирования, выявить основные тенденции его современного развития...
76722. Развитие лесного дела в период правления Петра І 130.51 KB
  Сведения о лесах встречаются в разных великокняжеских и царских грамотах некоторых других исторических и географических документах. Рыболовство в лесных озерах и реках охота и бортничество привлекало людей именно в леса.
76723. Индикаторы и динамика устойчивого экономического развития 3.74 MB
  В качестве наиболее общим индикаторов устойчивого развития принят интегральный показатель устойчивого развития, который основан на индексе развития человеческого потенциала. Система индикаторов устойчивого развития включает как общесистемные индикаторы, так и индикаторы...
76724. Вооруженные силы Московского государства в первой половине XVII века. «Полки нового строя» Алексея Михайловича 52.86 KB
  Во время войны они выступали с великим князем или с воеводами а в мирное время являлись помещиками и получали за службу земли в условное держание. В результате вассалитет князей и бояр был преобразован в государевых служилых людей за службу в условное держание реже в вотчину получавших поместья.
76725. Влияние и последствия применения допинга в большом спорте 38.13 KB
  Допинг – это лекарственные препараты, которые применяются спортсменами для искусственного, принудительного повышения работоспособности в период учебно-тренировочного процесса и соревновательной деятельности.
76726. Газопровод Саратов – Москва 81.7 KB
  История развития газовой отрасли в Саратовской области начинает свой отсчет с далекого 1906го года. В то время открытия месторождений газа как правило происходило совершенно случайно. Сын купца студент Рижского политехнического института понял что из скважины произошло выделение газа.
76727. Процесс развития личности и факторы, влияющие на него. Взаимовлияние внутренних и внешних, стихийных и управляемых факторов 103 KB
  Каждый человек проходит младенческую стадию развития, когда он учиться двигаться, говорить, мыслить. Точно так же каждый индивид развивается, как личность Формируется его мировоззрение и понимание мира. От этого будет зависеть его последующая роль в жизни общества.
76728. Трудовые ресурсы, персонал и трудовой потенциал организации 95 KB
  Современный трудовой коллектив представляет собой сложную социальную систему, где отдельные личности и группы людей взаимодействуют на принципах, весьма далеких от формально предписанных.