YaChudo

Двійкова купа

Переглядів: 0. Оновлено 26.10.2026.

Двійкова (min/max) купа
Типдвійкове дерево/купа
Винайдено1964
ВинайшлиJ. W. J. Williams
Обчислювальна складність
у записі великого О
Операція Середня Найгірша
Простір O(n) O(n)
Пошук O(n) O(n)
Вставляння O(1) O(log n)
Приклад неповної двійкової незростаючої купи. Наведено її представлення у вигляді масива.
Приклад неповної двійкової неспадної купи.

Двійкова купа[1] (англ. binary heap) — це структура даних, що є масивом, який можна розглядати як майже повне двійкове дерево. Кожен вузол цього дерева відповідає певному елементу масива. На всіх рівнях, крім можливо останнього, дерево повністю заповнене (заповнений рівень — такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо доти, доки в масиві не закінчаться елементи.

Для масиву A у корені дерева перебуває елемент A[1]. Далі дерево будується за наступним принципом: якщо якомусь вузлу відповідає індекс i, то індекс його батьківського вузла обчислюється за допомогою процедури Parent(i), індекс лівого дочірнього вузла — за допомогою процедури Left(i), а індекс правого дочірнього вузла — за допомогою процедури Right(i): 

Parent(i)
    return 
  
    
      
        ⌊
        
        i
        
          /
        
        2
        ⌋
      
    
    {\displaystyle \lfloor \;i/2\rfloor }
  


Left(i)
    return 
  
    
      
        2
        i
      
    
    {\displaystyle 2i}
  


Right(i)
    return 
  
    
      
        2
        i
        +
        1
      
    
    {\displaystyle 2i+1}

Розглядають два види бінарних куп: неспадні й незростаючі. В обох видах значення, що розташовані у вузлах купи, задовольняють властивості купи (англ. heap property). Властивість незростаючої купи (англ. max-heap property) полягає в тому, що для кожного вузла, крім кореневого виконується нерівність:

A [ P a r e n t ( i ) ] ⩾ A [ i ] {\displaystyle A[Parent(i)]\geqslant A[i]} .

Іншими словами, значення вузла не перевищує значення батьківського вузла. Таким чином найбільший елемент перебуває в корені дерева. Принцип побудови неспадної купи (англ. min-heap) протилежний. Властивість неспадної купи (англ. min-heap property) полягає в тому, що кожен елемент, крім кореневого, є не меншим за свій батьківський елемент:

A [ P a r e n t ( i ) ] ⩽ A [ i ] {\displaystyle A[Parent(i)]\leqslant A[i]} .

Підтримка властивостей купи

Підтримку властивості купи можна здійснювати за допомогою процедури Max_Heapify (для незростаючих бінарних куп). На вхід подається масив A й індекс i цього масиву. При виклику процедури Max_Heapify припускається, що бінарні дерева, коренями яких є елементи Left(i) і Right(i), є незростаючими купами, але сам елемент A[i] може бути меншим за його дочірні елементи і, таким чином, порушувати властивість незростаючої купи. Процедура Max_Heapify спускає значення елемента A[i] вниз по купі доти, доки дерево, в якому цей елемент буде коренем, не стане незростаючою бінарною купою: 

Max_Heapify(A,i)

 1 
  
    
      
        l
        ←
        
        L
        e
        f
        t
        (
        i
        )
      
    
    {\displaystyle l\gets \;Left(i)}
  

 2 
  
    
      
        r
        ←
        
        R
        i
        g
        h
        t
        (
        i
        )
      
    
    {\displaystyle r\gets \;Right(i)}
  

 3 if 
  
    
      
        l
        ≤
        
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
      
    
    {\displaystyle l\leq \;heap\_size[A]}
  
 and 
  
    
      
        A
        [
        l
        ]
        >
        A
        [
        i
        ]
      
    
    {\displaystyle A[l]>A[i]}
  

 4     then 
  
    
      
        l
        a
        r
        g
        e
        s
        t
        ←
        
        l
      
    
    {\displaystyle largest\gets \;l}
  

 5     else 
  
    
      
        l
        a
        r
        g
        e
        s
        t
        ←
        
        i
      
    
    {\displaystyle largest\gets \;i}
  

 6 if 
  
    
      
        r
        ≤
        
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
      
    
    {\displaystyle r\leq \;heap\_size[A]}
  
 and 
  
    
      
        A
        [
        r
        ]
        >
        A
        [
        l
        a
        r
        g
        e
        s
        t
        ]
      
    
    {\displaystyle A[r]>A[largest]}
  

 7     then 
  
    
      
        l
        a
        r
        g
        e
        s
        t
        ←
        
        r
      
    
    {\displaystyle largest\gets \;r}
  

 8 if 
  
    
      
        l
        a
        r
        g
        e
        s
        t
        ≠
        
        i
      
    
    {\displaystyle largest\neq \;i}
  

 9     then Swap 
  
    
      
        A
        [
        i
        ]
        ↔
        
        A
        [
        l
        a
        r
        g
        e
        s
        t
        ]
      
    
    {\displaystyle A[i]\leftrightarrow \;A[largest]}
  

 10         Max_Heapify(A,largest)

Час роботи процедури в найгіршому випадку пропорційний висоті купи. Якщо купа складається з n елементів, то її висота log2(n) . Тому оцінка часу роботи одного виклику Max_Heapify — O(log n).

Для підтримки властивості неспадної бінарної купи можна скористатись процедурою Min_Heapify. Вона подібна до Max_Heapify, тільки в рядках 3 і 6 алгоритму знак «>» треба замінити на «<».

Побудова купи

За допомогою процедури Max_Heapify можна перетворити масив A[1..n], де n = length[A], у незростаючу купу. Усі елементи підмасиву A [ ( ⌊ n / 2 ⌋ + 1 ) . . n ] {\displaystyle A[(\lfloor \;n/2\rfloor \;+1)..n]} є листами дерева, тому кожен із них можна вважати одноелементною купою, з якої можна почати процес побудови. Процедура Build_Max_Heap проходить по всіх інших вузлах і для кожного з них виконує процедуру Max_Heapify: 

Build_Max_Heap(A)

1 
  
    
      
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        ←
        
        l
        e
        n
        g
        t
        h
        [
        A
        ]
      
    
    {\displaystyle heap\_size[A]\gets \;length[A]}
  

2 for 
  
    
      
        i
        ←
        
        ⌊
        
        l
        e
        n
        g
        t
        h
        [
        A
        ]
        
          /
        
        2
        ⌋
      
    
    {\displaystyle i\gets \;\lfloor \;length[A]/2\rfloor }
  
 downto 1
3     do Max_Heapify(A,i)

Після завершення роботи процедури, масив A організується в незростаючу купу. Час роботи процедури Build_Max_Heap можна записати так:

O ( n ∑ h = 0 ⌊ log 2 ⁡ n ⌋ h 2 h ) = O ( n ∑ h = 0 ∞ h 2 h ) = O ( n ) {\displaystyle O\left(n\sum _{h=0}^{\lfloor \;\log _{2}n\rfloor }{\frac {h}{2^{h}}}\right)=O\left(n\sum _{h=0}^{\infty }{\frac {h}{2^{h}}}\right)=O(n)}

Для створення неспадної купи, необхідно замінити у третьому рядку алгоритму виклик Max_Heapify на Min_Heapify.

Алгоритм впорядкування купою

Робота алгоритму сортування купою починається з виклику процедури Build_Max_H, за допомогою якої з початкового масиву A[1..n] створюється незростаюча купа. Далі послідовно з купи виймається найбільший елемент, який міняють з останнім в купі. Після кожного обміну розмір купи зменшують на одиницю. В кінці отримують повністю відсортований неспадний масив: 

Heapsort(A)
1 Build_Max_Heap(A)
2 for 
  
    
      
        i
        ←
        
        l
        e
        n
        g
        t
        h
        [
        A
        ]
      
    
    {\displaystyle i\gets \;length[A]}
  
 downto 2
3     do Поміняти 
  
    
      
        A
        [
        1
        ]
        ↔
        
        A
        [
        i
        ]
      
    
    {\displaystyle A[1]\leftrightarrow \;A[i]}
  

4        
  
    
      
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        ←
        
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        −
        1
      
    
    {\displaystyle heap\_size[A]\gets \;heap\_size[A]-1}
  

5        Max_Heapify(A,1)

Час роботи процедури Heapsort рівний O(n log n), оскільки всього потрібно n-1 викликів Max_Heapify, кожен з яких працює за O(log n).

Черга з пріоритетами

Для того, щоб реалізувати на купі операції черги з пріоритетами використовують ще одну допоміжну процедуру Un_Max_Heapify(A,i). Ця процедура підтримує властивість незростаючої купи (аналогічно Un_Min_Heapify(A,i) для неспадної купи), за умови якщо властивість купи порушується в елементі з індексом i — він може бути більшим за батьківський елемент. При цьому припускається, що в усіх інших елементах властивість виконується і батьківський елемент i-го більший кожного з нащадків i-го елемента. Процедура «піднімає» елемент угору по дереву доти, доки він не перестане порушувати властивість купи: 

Un_Max_Heapify(A,i)
1 if i = 1
2    then return
3 if A[Parent(i)]<A[i]
4    then Поміняти 
  
    
      
        A
        [
        P
        a
        r
        e
        n
        t
        (
        i
        )
        ]
        ↔
        
        A
        [
        i
        ]
      
    
    {\displaystyle A[Parent(i)]\leftrightarrow \;A[i]}
  

5         Un_Max_Heapify(A,Parent(i))

Час роботи процедури — O ( l o g n ) {\displaystyle O(logn)} .

Процедура черги з пріоритетами Insert реалізується таким чином: у кінець купи дописується один елемент (при цьому розмір купи збільшується на 1), потім за допомогою Un_Max_Heapify цей елемент піднімається на необхідний рівень. 

Insert(A,x)
1 
  
    
      
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        ←
        
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        +
        1
      
    
    {\displaystyle heap\_size[A]\gets \;heap\_size[A]+1}
  

2 
  
    
      
        A
        [
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        ]
        ←
        
        x
      
    
    {\displaystyle A[heap\_size[A]]\gets \;x}
  

3 Un_Max_Heapify(A,heap_size[A])

Максимальний елемент перебуває в першому елементі купи, тому процедура Maximum реалізується тривіально: 

Maximum(A)
1 if heap_size[A] = 0
2    then Помилка "Черга пуста"
3    else return A[1]

У процедурі Extract_Max розмір купи зменшується на 1, останній елемент записується на місце першого (при цьому порушується властивість купи). Властивість купи відновлюється процедурою Max_Heapify. 

Extract_Max(A)
1 if heap_size[A] = 0
2    then Помилка "Черга пуста"
3 
  
    
      
        m
        a
        x
        ←
        
        A
        [
        1
        ]
      
    
    {\displaystyle max\gets \;A[1]}
  

4 
  
    
      
        A
        [
        1
        ]
        ←
        
        A
        [
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        ]
      
    
    {\displaystyle A[1]\gets \;A[heap\_size[A]]}
  

5 
  
    
      
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        ←
        
        h
        e
        a
        p
        _
        s
        i
        z
        e
        [
        A
        ]
        −
        1
      
    
    {\displaystyle heap\_size[A]\gets \;heap\_size[A]-1}
  

6 if heap_size[A] > 0
7    then Max_Heapify(A,1)
8 return max

У процедурі Change_Key можливі три варіанти:

  1. ключ елемента збільшився
  2. ключ елемента зменшився
  3. ключ елемента не змінився

Залежно від варіанту властивість купи після зміни ключа треба відновлювати або процедурою Un_Max_Heapify або процедурою Max_Heapify: 

Change_Key(A,i,k)

1 
  
    
      
        o
        l
        d
        _
        k
        e
        y
        ←
        
        A
        [
        i
        ]
      
    
    {\displaystyle old\_key\gets \;A[i]}
  

2 
  
    
      
        A
        [
        i
        ]
        ←
        
        k
      
    
    {\displaystyle A[i]\gets \;k}
  

3 if k>old_key
4     then Un_Max_Heapify(A,i)
5     elseif k < old_key
6            Max_Heapify(A,i)

Асимптотична складність операцій

Процедура Maximum виконується за O ( 1 ) {\displaystyle {\mathit {O(1)}}} , процедури Insert, Extract_Max, Change_Key виконуються за O ( log 2 ⁡ n ) {\displaystyle {\mathit {O(\log _{2}n)}}} .

Примітки

  1. ↑ Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.

Джерела


Інформаційні технології Це незавершена стаття про інформаційні технології.
Ви можете допомогти проєкту, виправивши або дописавши її.

Джерело: стаття у Вікіпедії та історія редагувань (автори).