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


 

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

34935. Классификации экономических циклов 27 KB
  Второй тип среднесрочные циклы продолжительностью 10 20 лет. В качестве причин средних циклов одни экономисты называли кредитную сферу Жугляр а также периодическое обновление производственных сооружений и жилья так называемые строительные циклы Кузнеца. Третий тип долгосрочные циклы большие экономические циклы Кондратьева продолжительностью 4855 лет.
34936. Классификация фирм 37 KB
  По цели деятельности фирмы бывают: коммерческая (цель – получение прибыли), некоммерческая(основная цель – социальная, получение прибыли не является основной целью)
34937. Коммерческие банки и их основные операции 26 KB
  Коммерческие банки выполняют следующие основные операции функции: 1. Собственные операции это фондовые операции банка с ценными бумагами т. Осуществление коммерческими банками операции подразделяются на пассивные и активные.
34938. Кредит и его формы 28 KB
  Кредитные отношения могут выражаться в разных формах кредита коммерческий кредит банковский кредит и др. Другие определения кредита: взаимоотношения между кредитором и заёмщиком; возвратное движение стоимости; движение платежных средств на началах возвратности; движение ссуженной стоимости; движение ссудного капитала; размещение и использование ресурсов на началах возвратности; предоставление настоящих денег взамен будущих денег и др. Формы кредита: На рынке реализуются две основные формы кредита: коммерческий и банковский....
34939. Макроэкономическое равновесие в трактовке классической и неокейсианской школ 31 KB
  Макроэкономическое равновесие в трактовке классической и неокейсианской школ Описывает поведение экономики Классическая школа: в долговой период Кейсианская: в краткосрочный Рассматривает условия Кля: для совершенной конкуренции Кейя: для несовершенной конкуренции Исходит из того что Кля: совокупный спрос = совокупному предложению т. Кейя: экономика может находиться в равновесии даже при неоптимальном использовании ресурсов. Экономика функционирует в условиях Кля: полной занятости всех ресурсов Кейя: недозагрузки. Рост экономики...
34940. Макроэкономическое равновесие и ее модель 27 KB
  Равновесие бывает краткосрочным текущим и долгосрочным. 2реальное равновесие которое существует в условиях несовершенной конкуренции и при наличии внешних эффектов. Различают: 1Частичное равновесие это равновесие установившееся в отдельных отраслях и сферах экономики.
34941. Методы экономической теории 29.5 KB
  Частные методы включают в себя следующие методы: графический; статистический; метод экономикоматематического моделирования; метод сравнительного анализа; экономический эксперимент.
34942. Монополия: сущность и виды 38 KB
  В силу объективных причин могут возникнуть: сырьевая монополия наличие единственного месторождения полезного ископаемого или иного экономического ресурса; административная монополия государственное регулирование в интересах общества экономического спроса некоторых товаров алкоголь оружие и т.; естественная монополия производство продукции одной фирмой обходится дешевле обществу чем двумя и более коммунальные службы. Наряду с естественными монополиями существуют и искусственные создаваемые за счет специальных мер:...
34943. Налоги. Понятие и виды 25.5 KB
  Понятие и виды Налоги это обязательные платежи взимаемые государством с физических и юридических лиц на основе специального законодательства. Налоги образуют источник бюджетных доходов; Функция перераспределения ресурсов между отраслями. Налоги стимулируют одни виды деятельности и ограничивают другие; Функция перераспределения доходов между членами общества и достижения социальной справедливости.