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


 

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

85375. Профілактика порушень слуху 39.23 KB
  Групи ризику дітей першого року життя по приглухуватості і глухоті: діти що народилися від багатоплідної вагітності; діти з масою тіла менше 15 кг; діти матері яких перенесли під час вагітності краснуху герпетичну інфекцію цитометоловірусну інфекцію; діти матері яких приймали під час вагітності ототоксичні препарати; діти що отримували в період новонародженості за вітальними свідченнями антибіотики ряду аміноглікозидів; діти слабочуючих або глухих батьків; діти з родовими травмами і внутрічерепним крововиливом. Ці діти...
85376. Предмет, завдання і методи логопедії та логопсихології 38.25 KB
  Найточнішим на сьогодні вважається таке визначення цієї науки: логопсихологія це галузь спеціальної психології в якій вивчається своєрідність психічного розвитку осіб з вадами мовлення первинного походження а також розробляються принципи і методи психокорекційної роботи з ними. Основною метою спеціального психологічного супроводу в системі освіти осіб з порушеннями мовлення є виявлення усунення і попередження дисбалансу між процесами навчання і розвитку цієї категорії та їх потенційними можливостями. З огляду на визначення логопсихології...
85377. Розвиток психіки глухої дитини. Розвиток словесно-логічного мислення і словесна пам’ять глухих дітей 38.39 KB
  Для першої I III класи характерний поширюється тип запамятовування тобто приріст відтвореного матеріалу від повторення до повторення. Для другої стадії IVVI класи характерний охоплює тип запамятовування при якому дитина розуміє і запамятовує загальний зміст тексту і ключові його слова а в подальшому поповнює його відсутніми елементами. Для третьої стадії розвитку словесної памяті VIIVIII класи характерно повне розуміння і запамятовування тексту. Часто спостерігається сплав осмисленого і механічного запамятовування: те що...
85378. Мониторинг воздействия на окружающую среду 67 KB
  Мониторинг воздействия на окружающую среду. Методы мониторинга воздействия на окружающую среду. Мониторинг воздействия на окружающую среду часть экологического мониторинга многоцелевая информационная система в задачи которой входит описание наблюдение оценка и прогноз источников воздействия на окружающую среду и отходов сбросы выбросы размещение и удаление отходов использование ресурсов и готовой продукции. Источник воздействия на окружающую среду ограниченная в пространстве область к которой могут быть отнесены все...
85379. Нормирование и лимитирование воздействия на окружающую среду 46.5 KB
  Нормативы воздействия на окружающую среду предельные характеристики источников воздействия на окружающую среду и условия размещения и удаления отходов соблюдение которых в любом случае не может привести к нарушению установленных критериев качества окружающей среды. Лимитирование воздействия на окружающую среду временное установление определенных характеристик источников воздействия на окружающую среду и отходов для соблюдения и контроля которых имеются необходимые возможности и средства. Лимиты воздействия на окружающую среду ...
85380. Распространение загрязняющих веществ 64 KB
  Если выбрасываемые в воздух примеси состоят из крупных частиц то распространяясь в атмосфере они под действием силы тяжести начинают спускаться с определенной постоянной скоростью в соответствии с законом Стокса. Естественно что почти все примеси в конечном итоге осаждаются на поверхности земли причем тяжелые осаждаются в основном под действием гравитационного поля а легкие в результате диффузионного процесса. Поскольку наиболее опасны для окружающей среды примеси газообразного вида типа окислов то именно таким легким соединениям...
85381. Нормирование качества воздуха, воды, почвы 67.5 KB
  Совершенно недопустимо сравнивать уровни загрязнения селитебной зоны с установленными ПДКрз а также говорить о ПДК в воздухе вообще не уточняя о каком нормативе идет речь. Уровень загрязнения атмосферы обычно описывается набором статических характеристик для ряда измеряемых вредных веществ. Для оценки степени загрязнения атмосферы средние максимальные концентрации веществ нормируются на величину средней максимальной концентрации для большого региона или на санитарногигиснический норматив ПДК. Нормированные характеристики загрязнения...
85382. Организация экоаналитического контроля 53 KB
  Контролируемые объекты и компоненты в экоаналитическом контроле Организация и обеспечение ЭАК требуют решения комплекса взаимосвязанных проблем которые образуют приведенную ниже единую систему: Нормативнотехническое обеспечение и правовая регламентация Контролируемые объекты и компоненты Методическое обеспечение Аппаратурное обеспечение Метрологическое обеспечение Обеспечение качества химической информации Кадровое обеспечение Нормативнотехническое обеспечение и правовая регламентация системы ЭАК С точки зрения природоохранительного...
85383. Требования к средствам измерения и классификация экоаналитических средств 35.5 KB
  Требования к средствам измерений Различными нормативными документами в области обеспечения единства измерений предъявляется достаточно жесткие требования к средствам измерений СИ применяемым при экоаналитических работах. Прежде всего СИ должны пройти испытания с целью утверждения типа средств измерений. После получения положительного результата испытаний такие средства измерений включаются в установленном порядке в Государственный реестр средств измерений При эксплуатации СИ необходимо соблюдать установленную в техническом паспорте СИ...