4877

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

Лекция

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

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

Русский

2012-11-28

73.5 KB

48 чел.

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

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


 

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

34006. Основные антропологические парадигмы 31.5 KB
  Проблема человека одна из центральных тем философии. В разных философских традициях и школах по разному трактуется феномен человека. Христианская антропология зиждется на ряде основополагающих постулатов: а человек есть триединство духовного душевного и телесного;б человек есть образ и подобие Божие;в онтологическая ущербность человека наступившая после грехопадения прародителей человечества Адама и Евы;г онтологический грех человека искупается жертвенной смертью Иисуса Христа каждый имеющий в своем сердце веру в Спасителя...
34007. Человек как духовное существо. Проблема смысла жизни, смерти и бессмертия 24 KB
  И эта неудовлетворенность содержит в себе причины творческой деятельности Поэтому призвание задача каждого человека всесторонне развивать все свои способности и по мере возможностей вносить свой личный вклад в историю в прогресс общества его культуры. Смысл жизни общва и челтва в целом. Буддизм: чел живет для того чтобы прервать цепь перерождений и никогда больше не возрождаться. Христво восхождением чел к богу.
34008. Этология Конрада Лоренца 34.5 KB
  Изучая поведение разных животных и человека К.Зонди 18931986 швейцарский ученый развивая и продолжая традиции психоанализа наряду с индивидуальным и коллективным бессознательным выделил понятие родового бессознательного это влияние наследственности и рода предков на судьбу человека. Навязанная судьба которая складывается: а под влиянием генетической наследственности; б под действием генотрофизма развития психики человека под влиянием того или иного предка или родственника от которых может зависеть выбор профессии хобби...
34009. Религия как социокультурный феномен. Понятие Бога в философии и религии 40.5 KB
  Понятие Бога в философии и религии. Философия религии важный раздел философского знания поскольку религия составляет системообразующий элемент различных культур цивилизаций и обществ. Философию религии нельзя также отождествлять с религиозной философией. Философия религии это прежде всего рефлексия над религией как сложным социокультурным феноменом определение ее знания в жизни человека и общества.
34010. Предмет и задачи этики. Основные этические системы 44 KB
  Вся совокупность проблем в той или иной мере посвященных изучению этих вопросов была представлена особой философской теорией получившей название философия морали нравственности или этика. Термин этика происходит от древнегреческого слова ethos этос подразумевавший пространство совместного проживания людей или животных дом звериное логово птичье гнездо и т. Поэтому термин этика также введенный в употребление Аристотелем изначально приобрел двоякую направленность: 1 обозначение совокупности добродетелей правил и норм...
34011. Основные этические системы 46.5 KB
  Остановимся на нескольких наиболее значительных и как нам представляется не утративших свое значение и по настоящее время именно в силу своей вневременной универсальной значимости для нравственного сознания человека: гедонизме стоицизме этике долга и этике любви. Именно такая постановка личности по Эпикуру порождает три степени свободы каждая из которых есть в сущности ничто иное как освобождение человека от тяжелых экзистенциальных переживаний сопровождающих его на протяжении всей жизни: от страха перед Богами от страха перед...
34012. Искусство как социокультурное явление.Эстетические основания и закономерности развития ис 45.5 KB
  Искусство это одна из форм культуры и сфера художественного творчества. философия исследует искусство в общем плане и в контексте жизни человека и общества. Искусство отражает и изображает жизнь в художественных образах которые позволяют человеку непосредственно в чувственном виде переживать то что в них заключил художник.
34013. Философское понимание культуры. Культура и цивилизация 26 KB
  Культура и цивилизация. Культура все созданное человеком; совокупность созданных и создаваемых человеком ценностей; качественная характеристика уровня развития ова. Там где есть человек его деятсть отношения между людьми там имеется и культура. Культура: материальная и духовная не противопоставлять.
34014. Филсофия Древней Индии 23 KB
  э Мир вечен никем никогда не был создан остоянно развивается делится на мир приоды и мир людей. Мир природы гормоничен и спокоен; мир людей мир страданий.э Мир вечен никем никогда не создан. Сущность мира изменеие развия.