4877

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

Лекция

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

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

Русский

2012-11-28

73.5 KB

44 чел.

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

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


 

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

28685. Военная реформа 1924 - 1925 гг. Создание территориально-милиционной системы и укрепление кадрового состава Красной Армии 12.76 KB
  Вместо единого Штаба Рабочекрестьянской красной Армии создано 3 самостх управления: Штаб РККА Главное Управление РККА и Инспекторат РККА. Штаб РККА становится основным органом управления в системе военного ведомства на котй возлагались задачи разработки общих вопросов обороны на случай войны. управление ГУ РККА возлагались задачи управления текущей жизнью армии и обеспечения ее повседневных нужд. Инспекторат РККА ведал боевой подготовкой войск и командного состава а также инспектированием Вооруженных сил.
28686. Реконструкция сельского хозяйства. Совершенствование форм управления промышленностью, и сельским хозяйством в конце 20-х - начале 30-х гг. 13.37 KB
  Совершенствование форм управления промышленностью и сельским хозяйством в конце 20х начале 30х гг. С этого времени косвенное регулирование вытесняется элементами непосредственного управления. На место функциональной системы управления экономикой пришел отраслевой и производственнотерриториальный принцип.
28687. Мероприятия партии и правительства по проведению коллективизации: плюсы и минусы 12.53 KB
  началась массовая коллективизация заготовительная компания приняла насильственный характер рыночные механизмы были сломлены. сплошная коллективизация должна была завершиться на Северном Кавказе Нижнем и Среднем Поволжье. Принудительная коллективизация вызвала забой скота и падение урожаев а выкачивание хлеба из села выросло.
28688. Попытка установления парламентской монархии в 1-ом десятилетии XX в 14.11 KB
  Об учреждении Госой думы и Положение о выборах в нее Манифест 17 окт. Об усовершенствовании госного порядка и Осные законы от 23 апр. Согласно августовским Манифесту и Положению Гос. К компетенции Думы относились: разработка и обсуждение законов обсуждение госго бюджета и др.
28689. Изменение в государственном строе России в результате первой русской буржуазной революции. Новые избирательные законы 13.43 KB
  Изменение в государственном строе России в результате первой русской буржуазной революции. Основным событием явилось создание представительного органа Государственной думы. был подписан Манифест об учреждении Госной думы. В законе указывалось что она формируется для предварительной разработки и обсуждения законопроектов коте в дальнейшем должны поступать в Госный совет.
28690. Государственные Думы и их классовый состав. Обсуждение аграрного вопроса на них 13.76 KB
  Государственные Думы и их классовый состав. Первое заседание Государственной думы состоялось 27 апреля 1906 года в Таврическом дворце СанктПетербурга. Обсуждались 2 проекта по аграрному вопросу: от кадетов 42 подписи и от депутатов трудовой группы Думы 104 подписи. Трудовики требовали для обеспечя крестьян отвести им участки по трудовой норме за счет казенных удельных монастырских и частновладельческих земель превышающих трудовую норму введение уравнительнотрудового землепользя объявления политой амнистии ликвидации Госного...
28691. Столыпинская аграрная реформа и ее сущность 12.71 KB
  Столы́пинская агра́рная рефо́рма реформа крестьянского надельного землевладения в России проходившая с 1906 по 1917 гг. укрепление Крестьянского банка принудительное землеустройство законы от 14 июня 1910 и 29 мая 1911 и усиление переселенческой политики перемещение сельского населения центральных районов России на постоянное жительство в малонаселенные окраинные местности Сибирь Дальний Восток и Степной край как средство внутр. колонизации были направлены на ликвидацию крестьянского малоземелья интенсификацию хозной деятсти...
28692. Российская империя в годы первой мировой войны (1914-1918 гг.) 13.05 KB
  Российская империя в годы первой мировой войны 19141918 гг. В годы войны в составе правительства происходили частные смены как отдельных министров так и председателя Совета министров. Еще в начальный период войны патриотический подъем вызвал создание Всероссийского земского союза помощи раненым и Всероссийского союза городов.
28693. Изменение в государственном аппарате России в годы первой мировой войны: особые совещания, военно-промышленные комитеты, из роль и значение 13.13 KB
  Изменение в государственном аппарате России в годы первой мировой войны: особые совещания военнопромышленные комитеты из роль и значение. В качве новых форм управления промышленностью и капиталами были созданы военнопромышленные комитеты в задачи которых входило распределение военных заказов установление внутренней и внешней ценовой политики. было образовано более 200 областных и местных военнопромх комитетов во главе котх стоял Центральный военнопромышленный комитет. В состав Центрго военнопромго комитета входили представители...