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


 

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

78524. Физический уровень сетевых телекоммуникаций: общие понятия, типы и характеристики линий связи, методы передачи данных 27 KB
  Физический уровень сетевых телекоммуникаций: общие понятия типы и характеристики линий связи методы передачи данных Физ. В зависимости от типа физической среды передачи информации линии связи могут быть либо кабельными проводными либо беспроводными электромагнитные волны. в оптоволоконном кабеле для передачи данных используются световые импульсы. малую надежность передачи информации.
78525. Базовые сетевые технологии: стандарты, механизмы, характеристики 27 KB
  Под топологией компьютерной сети обычно понимают физическое расположение компьютеров сети относительно Друг Друга и способ соединения их линиями. Топология определяет требования к оборудованию тип используемого кабеля методы управления обменом надежность работы возможность расширения сети. Звезда: все компьютеры сети соединяются с центральным компьютером активная звезда при отсутствии центрального компьютера – псевдо звезда. По сети непрерывно циркулирует маркер который имеет длину 3 байта и не содержит обычных данных.
78526. Конструирование путевых машин капитального ремонта пути 1007.73 KB
  От его работы зависит бесперебойная работа всех его секторов. Железнодорожный транспорт многоотраслевое хозяйство представлявшее собой огромный по протяженности конвейер бесперебойная и безаварийная работа которого зависит от функционирования каждой из его составных частей. Железнодорожный путь работает в самых сложных атмосферноклиматических условиях при постоянном воздействии динамической нагрузки от проходящих поездов. Для обеспечения указанных требований постоянно ведутся работы по усилению несущей способности и...
78527. Технология производства рабочей лопатки турбины 4.23 MB
  Одной из самых нагруженных деталью, ограничивающей межремонтный ресурс, являются неохлаждаемые лопатки турбины, изготавливаемые из деформируемого никелевого сплава ЭИ893. Лопатки из этого сплава из-за ограничений по длительной прочности имеют ресурс 48000 часов.
78528. Построение системы управления поставками и маркетинга для крупного металлургического холдинга «КарМет» 19.86 MB
  Традиционные информационные системы изначально были функциональной основой для множества организаций или функциональных сфер, но не могли объединять их в случае их географической распределенности. Одну и ту де информацию собирали многократно и во многих местах, и она была недоступна в реальном времени.
78529. Расчет и проектирование объемной гидропередачи привода рабочего органа дорожно-строительной машины 1.02 MB
  В настоящее время гидропривод широко применяется в авиационной, станкостроительной, тракторостроительной, металлургической и многих других отраслях промышленности. Гидропривод широко применяется также в тяжелых грузоподъемных машинах и самоходных агрегатах.
78530. Расчет путевода улицы Ленинградская 590.91 KB
  Условия движения особенно в городах характеризуются все возрастающей сложностью. Высокая и все увеличивающаяся интенсивность движения – результат диспропорции между ростом автомобильного парка и сетью автомобильных дорог. Высокий уровень аварийности связанный с человеческим фактором – результат диспропорции между уровнями подготовки и транспортной культуры участников движения и массовости профессий водителя. Увеличение интенсивности изменение структуры и скоростных режимов транспортных потоков предъявляют все более жесткие требования к...
78532. Газоснабжение села Петровка Золочевского района 301.18 KB
  Тема дипломного проекта посвящена актуальным вопросам газоснабжения и эксплуатации объектов газоснабжения сельских населенных пунктов. Газификация жилищно-коммунальных и производственных объектов позволяет повысить уровень благоустройства жилого фонда...