Bevezetés
Régen programoztam már utoljára. Múlt héten gondoltam egyet, és megírtam C# nyelven a HeapSort algoritmust (magyarul kupacrendező algoritmust), mert jó szórakozás, hasznos, továbbá azért is, hogy leírhassam a blogomon a működését. A teljesség vagy a pontosság igénye nélkül – próbáltam mindent leírni, amit tudok, de nem vagyok még ennek a témának a szakértője.
A HeapSort egy rendezőalgoritmus, azaz fog egy tetszőleges elemekből álló tömböt (számsort) és sorba rendezi az elemeket. Ez egy egyszerű, de érdekes algoritmus, több okból is.
- A rendezőalgoritmusok mind érdekesek, ugyanis nem tehetjük azt meg, hogy minden elemet minden elemmel összehasonlítunk, mert az n * (n – 1) / 2 összehasonlítást igényelne és az algoritmushoz szükséges műveletek száma négyzetesen arányos lenne az elemek számával.
Az első diagramm mutatja, hogy optimálisan mennyi művelet elvégzésére van szükség az adatok arányában. A második diagrammon látszik, hogy ha a kettő négyzetesen arányos, akkor egy bizonyos adatmennyiség felett elfogadhatatlanul sok művelet elvégzésére van szükség, irtózatosan lelassul a program. - Rendezőalgoritmusoknál megint csak nem tehetjük meg azt, hogy egy sorozatba “beszúrunk” egy elemet, ugyanis az azt jelenti, hogy a beszúrt elemet követő összes többi elemet eggyel odébb toljuk. Például a következő számsorozatban a 4. helyre szúrjuk be az 5-ös számot.
3 6 2 6 8 12 4 3 6 3 6 2 5 6 8 12 4 3 6 Az ilyen beszúrásokhoz szükséges műveletek összeadódnak, így ha több ilyet is elvégzünk, akkor megint egy négyzetesen romló teljesítményű algoritmust kapunk.
- Konkrétan a HeapSort algoritmus a sorozatra nem (csak) úgy tekint, mint egy sorozatra, hanem mint egy hierarchikus rendszerre, de ezt majd bővebben kifejtem.
- Ha valakit érdekel a programozás, akkor mindenképp ajánlott tanulmányoznia ezt az algoritmust.
Definíciók
Először is tudni kell, mi az a bináris fa [binary tree]. A bináris fa egy elemeket (itt például számokat) tartalmazó hierarchikus rendszer, melyben van egy gyökér vagy kezdő elem [root node] és minden elemnek van legfeljebb kettő gyerek-eleme [child node]. Ábrázolva jobban megérthető.
Az elemek mélységén a gyökér mért távolságot kell érteni. A bináris fa mélysége a legmélyebben lévő elem mélységével egyezik meg. Az ábrán több n mélységű bináris fa látható (kékkel az adott sorok mélysége van jelölve).
Egy bináris fa kiegyensúlyozott [balanced], ha 0-tól n-2 mélységig minden elemnek van 2 gyerek-eleme, azaz csak a legalsó sorból hiányoznak elemek. A fenti ábrán az első kettő kiegyensúlyozott bináris fa, a harmadik esetében viszont az n-1-ik sorból hiányzik egy elem.
Egy n mélységű bináris fa balra tömörített [left justified], ha minden k < n esetén k mélységben 2k eleme van, és n mélységben az elemek balról jobbra hézagmentesen vannak elhelyezve.
Az első bináris fa balra tömörített, a második nem.
Na és itt érkeztünk el egy fontos definícióhoz.
Egy heap (nagyjából azt jelenti, hogy kupac, az egyetemeken is így fordítják le, de annyira hülyén hangzik, hogy komoly munka állhatott az elnevezés mögött, mert ennyire hülye nevet kapásból nem lehet adni – mindegy…), szóval egy heap egy olyan bináris fa, ami egyszerre kiegyensúlyozott és balra tömörített, másképpen mondva, ha az elemeket egyenként adnánk hozzá, akkor mindig fel kell tölteni az adott sort mielőtt újabb sorba kezdenénk, és minden sort balról jobbra kell feltölteni.
Ezen kívül van egy olyan is, hogy heap property vagy kupactulajdonság, amit lehet érteni a heap egy elemére vagy az egész heapre. A heap egy eleme akkor bír a kupactulajdonsággal, ha az adott elem nagyobb vagy egyenlő a gyerek-elemeinek értékével (ha nincs gyerek-eleme, akkor úgy kell tekinteni, mintha az kisebb lenne). A teljes heap akkor rendelkezik a kupactulajdonsággal, ha minden eleme rendelkezik vele.
Az első két példán a kék elem rendelkezik a kupactulajdonsággal, a harmadik esetben nem.
A haditerv
Most, hogy megvolt a bevezető és tudjátok, mi az a bináris fa és heap, azt fogom leírni:
- Hogyan lehet egy bináris fát heappé alakítani
- Hogyan lehet egy bizonyos változás után újra heappé alakítani
- Hogyan lehet mindennek köze a sorbarendezéshez, ami be volt ígérve
- Hogyan lehet ezt tömbökre alkalmazni minél hatékonyabban
Bináris fa → Heap
Előszöris a bináris fát úgy készítjük el, hogy minden sort balról jobbra töltünk fel, és ha már nincs több hely, csak akkor kezdünk újabb sort, így egy kiegyensúlyozott, balra tömörített bináris fát kapunk, lásd az alábbi ábrán.
Ha egy bináris fa egyik eleme nem rendelkezik a kupactulajdonsággal (azaz van egy gyereke, aminek nagyobb az értéke), akkor az előbbi elemnek úgy adhatunk kupactulajdonságot, hogy az értékét felcseréljük a nagyobbik gyerekének az értékével. Ezt a műveletet süllyesztésnek [sift-down/bubble-down] nevezzük.
Mivel a nagyobbik gyerekének az értékével cseréltük fel, ezért (most már) a másik gyerek mindenképp kisebb a szülőjénél, nem kell vele foglalkozni. A nagyobbik gyerek (amivel az eredeti elemet felcseréltük) gyerekei viszont elveszthették a kupactulajdonságukat, mert a szülőjük értéke csökkent, potenciálisan valamelyik gyerekének az értéke alá. Ilyenkor ezt az elemet még lejjebb kell süllyeszteni, és ezt addig ismételni amíg nem rendelkezik az adott elem a kupactulajdonsággal, vagy amíg a kupac aljára nem érünk.
A süllyesztés kóddal leírva:
süllyeszt (elem) {
if ((elem < elem→első_gyereke) && (elem→második_gyereke < elem→első_gyereke)) {
felcserél (elem, elem→első_gyereke)
süllyeszt (elem→első_gyereke)
}
if (elem < elem→második_gyerek) {
felcserél (elem, elem→második_gyereke)
süllyeszt (elem→második_gyereke)
}
// Ha egyik gyerek sem nagyobb, nem csinálunk semmit
}
Ennek a fordítottja, amikor az alul lévő elemet cseréljük fel a szülőjével, ha a szülő kisebb értékű (és a másik gyerek sem nagyobb) – és ezt ismételgetjük, amíg kell; ennek a neve feljebb-buborékoltatás [sift-up/bubble-up]. Ezt használjuk akkor, ha egy kész heaphez új elemet adunk. Ha a heaphez új elem adásakor azt mindig megfelelően buborékoltatjuk, csak azt kell ellenőrizni, hogy a szülő kisebb-e, az új elem testvére ugyanis automatikusan kisebb a szülőnél.
A buborékoltatás kóddal leírva:
buborékoltat (elem) {
if (elem→szülője < elem) {
felcserél (elem→szülője, elem)
buborékoltat (elem→szülője)
}
// Ha a szülő nem kisebb, nem csinálunk semmit
}
Ha megfelelően süllyesztünk minden elemet, aminek gyereke van, vagy minden új elem hozzáadásakor azt feljebb-buborékoltatjuk, akkor a művelet végeztével az egész heap rendelkezni fog a kupactulajdonsággal.
Heap → első elem eltávolítása → heap
A sorbarendezésnél fontos szerepet fog játszani az a lépés, hogy az első elemet (ami nyilván a legnagyobb értékű eleme a kupacnak) eltávolítjuk. Ekkor a heap egy olyan bináris fává alakul, ami se nem balra tömörített, se nem kiegyensúlyozott. Ezt a problémát úgy javítjuk ki, hogy a legutolsó elemet áthelyezzük az első helyre. Itt van rá egy példa:
Ekkor viszont látszik, hogy az új elem nem rendelkezik a kupactulajdonsággal (a többi elemhez szándékosan nem nyúltunk). A kupactulajdonságot a már leírt süllyesztéssel állíthatjuk vissza, azaz az első elemet addig cserélgetjük a nagyobbik gyerekével, amíg lehet.
Pár lépésből visszaállítottuk az egész bináris fa kupactulajdonságát és újra a legnagyobb (vagy egyenlőség esetén az egyik legnagyobb) elem áll az első helyen.
A kupactulajdonság visszaállítása kóddal leírva mindössze egy sor:
süllyeszt (kezdő_elem)
Ezzel a módszerrel – ha folyamatosan eltávolítjuk az aktuális legnagyobb elemet -, akkor az elemeket végső soron csökkenő sorrendben távolítottuk el, azaz sorbarendeztük őket. De még nem vagyunk kész, ugyanis egy tömböt akartunk rendezni eleve és nem egy bináris fát.
Sorbarendezés az eddigi ismeretek alapján
Most jön az a rész, amikor az egész triviális programműveletekkel leírhatóvá válik.
- Mivel a heap egy kiegyensúlyozott és balra tömörített bináris fa, tömbként is lehet kezelhetem, magyarul “heapesítem/kupacosítom” a tömböt.
- Minden művelet, amit a kupacon végzünk el, leírható egy tömbön végzett műveletként.
- A sorbarendező-program tehát így fog kinézni:
- Kupacosítom a sorbarendezendő tömb elemeit és definiálok1 egy azonos hosszúságú tömböt, amiben sorbe fogom rendezni az elemeket
- A következőket addig ismétlem, amíg a kupacosított tömb el nem fogy:
- A kupac legnagyobb/első elemét berakom a sorbarendezett tömb utolsó üres helyére
- Eltávolítom a kupac első elemét, majd visszaállítom a kupactulajdonságot
- A másik1 tömbben növekvő sorrendben szerepel az összes elem, kész vagyok.
(1: Valójában nem definiálok külön tömböt, majd leírom, miért nem.)
Tömb → heap
Egy tömb elemeit egyszerűen hozzárendelhetjük egy heap elmeihez: sorszámozzuk a heap elemeit olvasási sorrendben (balról jobbra, fentről lefele) 0-val kezdve. Példának itt van egy heap vizuálisan ábrázolva és tömb formájában.
| Index a tömbben | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| Érték | 25 | 22 | 17 | 19 | 22 | 14 | 15 | 18 | 14 | 21 | 3 | 9 | 11 |
Látszik, hogy a tömb minden n.-ik elemének (tömb[n]) az első gyereke tömb[2 * n + 1], a második gyereke pedig tömb[2 * n + 2]. Ebből visszaszámolva tömb[k] szülője tömb[floor(k / 2 – 0,5)], ahol a floor lefelé kerekítést jelent. Például tömb[4] = 22 első gyereke tömb[9] = 21, második gyereke pedig tömb[10] = 3.
Most lássuk, hogyan kell egy tömbbel dolgozva eltávolítani a kupac gyökerét. Tudjuk, hogy a gyökér az tömb[0] és az utolsó sorban lévő utolsó eleme a kupacnak pedig a tömb legutolsó eleme (tömb[tömb.hossz – 1]). Mivel az utolsó elemet a következő lépésben úgyis előrehoznánk, cseréljük fel a kettőt, és tegyünk úgy mint ha az utolsó elem már nem lenne a tömb és a kupac része. Az előző példát továbbvezetve így néz ki a művelet:
| Eredeti tömb | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| Érték | 25 | 22 | 17 | 19 | 22 | 14 | 15 | 18 | 14 | 21 | 3 | 9 | 11 |
| A csere után | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| Érték | 11 | 22 | 17 | 19 | 22 | 14 | 15 | 18 | 14 | 21 | 3 | 9 | 25 |
Az “úgy teszünk” rész alatt azt értem, hogy egy külön változóban (mondjuk heapHossz) tároljuk, hogy a tömb első hány elemére kell úgy tekinteni, mint a heap elemére. Miután ezt tudjuk, a tömb aktív részének visszaállítjuk a kupactulajdonságát (az első elemet lejjebb süllyesztjük.) A következő ábra és a táblázatok ezt mutatják heapre, illetve tömbre vetítve.
| Kiinduló állapot | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| Érték | 11 | 22 | 17 | 19 | 22 | 14 | 15 | 18 | 14 | 21 | 3 | 9 | 25 |
| 1. süllyesztés | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| Érték | 22 | 11 | 17 | 19 | 22 | 14 | 15 | 18 | 14 | 21 | 3 | 9 | 25 |
| 2. süllyesztés | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| Érték | 22 | 22 | 17 | 19 | 11 | 14 | 15 | 18 | 14 | 21 | 3 | 9 | 25 |
| Végállapot | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| Érték | 22 | 22 | 17 | 19 | 21 | 14 | 15 | 18 | 14 | 11 | 3 | 9 | 25 |
Ugyanezt ismételgetve a tömb végében gyűlnek a legnagyobb értékek, és a legvégén, amikor heapHossz = 0 lesz, a tömb növekvő sorrendben tárolja az értékeket. Ezért nincs szükség arra, hogy tényleg külön tömböt definiáljuk a sorbarendezett értékek számára.
A táblázatban minden sor azt a lépéssort jelöli, melyben a kupac legnagyobb elemét hátraküldjük, majd a kupactulajdonságot visszaállítjuk. Dőlt zölddel van jelölve a a tömb végén lévő sorbarendezett számsor és félkövér kékkel azok az elemek, melyek át lettek helyezve a kupactulajdonság visszaállítása közben.
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] | [11] | [12] |
| 22 | 22 | 17 | 19 | 21 | 14 | 15 | 18 | 14 | 11 | 3 | 9 | 25 |
| 22 | 21 | 17 | 19 | 11 | 14 | 15 | 18 | 14 | 9 | 3 | 22 | 25 |
| … | ||||||||||||
| 9 | 3 | 11 | 14 | 14 | 15 | 17 | 18 | 19 | 21 | 22 | 22 | 25 |
| 3 | 9 | 11 | 14 | 14 | 15 | 17 | 18 | 19 | 21 | 22 | 22 | 25 |
| 3 | 9 | 11 | 14 | 14 | 15 | 17 | 18 | 19 | 21 | 22 | 22 | 25 |
A teljes program valahogy így írható le:
int[] tömb = ...;
int tömbHossz = tömb.hossz;
int kupacRendezés() {
kupacosít(floor(tömbHossz / 2 - 0,5));
while(tömbHossz != 0) {
tömbHossz = tömbHossz - 1
felcserél(0, tömbHossz)
süllyeszt(0)
}
}
kupacosít(int kezdőszám) {
for (; 0 <= kezdőszám; kezdőszám = kezdőszám - 1) {
süllyeszt(kezdőszám)
}
}
süllyeszt(int elem_index) {
if (tömb[elem_index] < tömb[elem_index * 2 + 1] &&
tömb[elem_index * 2 + 2] < tömb[elem_index * 2 + 1]) {
felcserél(elem_index, elem_index * 2 + 1)
süllyeszt(elem_index * 2 + 1)
return
}
if (tömb[elem_index] < tömb[elem_index * 2 + 2]) {
felcserél(elem_index, elem_index * 2 + 2)
süllyeszt(elem_index * 2 + 2)
}
}
felcserél(int a, int b) {
int tmp = tömb[a]
tömb[a] = tömb[b]
tömb[b] = tmp
}
Összegzés
Tanulságok
A programot megírtam, de most, hogy arról írok, hogyan működik a program, olyan érzésem van, mint amikor pár éve először elolvastam pár HTML-tutorialt és pár hétre-hónapra rá már olyan bejegyzéseket írtam, hogy “Hogyan készítsünk magunknak profi kinézetű honlapot.” Pontosabban érzem, hogy erről a mostani írásomról is hasonlókat fogok gondolni két év múlva, mint most a régebbi ilyen írásaimról. Most megcsináltam valamit, de máris úgy írok róla, mintha olyan hű de nagyon jól értenék az elmélethez. Pedig nem, csak jól álcázom.
Én így tanulok. A bejegyzés írása közben jöttem rá fokozatosan arra, hogy egy csomó helyen lehet egyszerűsíteni/gyorsítani az algoritmust (a siftDown(int) eredeti verzióját össze lehet hasonlítani a lentebbi végleges verzióval). Ha bármiben tévedtem, javítsatok ki, én azzal is okosodok, előre is köszönöm.
Köszönöm
Az algoritmussal először nem tudom mikor találkoztam, de a megértéseben egy prezentáció [kelt 2004. márc. 18-án] segített először. Amúgy a linkelt honlap és a többi prezentáció egy kész aranybánya, ajánlom megtekintését. Továbbá: Wikipedia. Végül, de nem utolsó sorban köszönet Fegyinek a segítségért.
Letöltés
Természetesen elkészítettem a valódi verzióját is a fentieknek, a linkre kattintva letölthető C# nyelven. Visual Studio 2008-al megnyitva biztosan működik, Visual C# Expressel is kéne, hogy működjön, de ezt nem tudtam leellenőrizni.
A program lényegi része a HeapSorter osztályban van, és lényegében megegyezik a fentebb leírt pszeudokóddal, de azért van pár eltérés, mint például angol névhasználat (ami nem tudom mennyire elfogadott itthon, de én angolul szoktam meg a programozást), pár teljesítményoptimalizáció, array bound checking és IComparable használata int helyett. A HeapSorter osztály akár módosítás nélkül felhasználható más programokban is.
Van egy Program osztály is, ez tulajdonképpen csak azt teszi lehetővé, hogy ki lehessen használni a HeapSorter funkcionalitását. Parancssorból lehet futtatni és 3 paramétert fogad el. Az első paraméter egy 32-bites szám, a program egy ekkora méretű tömböt hoz létre (alapbeállítás = 1000), a második szintén egy 32 bites szám, a program az előző tömböt maximum ekkora (alapbeállítás = 10000), véletlenszerű számokkal tölti fel és rendezi a QuickSort algoritmus szerint. A harmadik paraméter azt határozza meg, hogy a parancssorban milyen adatokat írjon ki a program (logikailag kombinálható paraméter):
- None vagy 0: rendezi a tömböt és nem ír ki semmit
- Heap vagy 1: először heapbe rendezi a tömböt, majd kiírja a struktúrát a parancssorra
- SortedArray vagy 2: kiírja a parancssorra a rendezett tömböt (ez az alapbeállítás)
- Beep vagy 4: hanggal jelzi, ha tömb heappé alakítása (Heap paraméter esetén) és a sorbarendezés véget ért
- Events vagy 8: kiírja a sorbarendezés közbeni heap-alakokat
- Ezek valamely összegére a program úgy tekint, mint ha az összes tag meg lenne adva önálló paraméterként (pl. a 3-at úgy értelmezi, hogy 1 és 2; a 7-et úgy, hogy 1+2+4; stb.)
- Time vagy 256: A többi opciót figyelmen kívül hagyva csak a QuickSort algoritmus szerint sorbarendezi a tömb elemeit és kiírja a parancsorra az igénybe vett időt
Pédák a program futtatására:
- heapsort 100 1000 None – 100 darab 1–1000 közti számot rendezzen sorba, a parancssorra semmit ne írjon ki
- heapsort 500 2000 Heap – 500 db 1–2000 közti számot rendezzen heapbe és írja ki a parancssorra
- heapsort 10000 5000000 Time – írja ki a parancssorra, mennyi időbe telik 10000 db 1–5 000 000 közti számot sorba rakni
- heapsort 100 10000 10 > data.txt – írja ki a data.txt fájlba a sorbrendezés közbeni heap-variációkat és a sorbarendezett számokat (10 = 2 + 8) 100 db 1–10000 közti számot
Túlságosan nagy méretű tömb esetén a program kifogyhat a rendelkezésre álló memóriából. Ilyenkor a program elegánsan összeomlik, próbálkozz kisebb tömbbel (nálam négyszázötven-millió elem alatt van a határ).
A teljesítményről annyit, hogy elég gyors, de az analízishez nem annyira értek, legyen annyi elég, hogy a kupacrendezés elvi futásideje O(n logn) és pár mérés alapján egy loglineáris görbe nagyjából illeszthető a mérési pontokra.
| x (elemek száma) | 500 000 | 1 000 000 | 5 000 000 | 10 000 000 | 100 000 000 | 200 000 000 | 300 000 000 |
| t (ms) | 615 | 1400 | 9 100 | 19 700 | 284 000 | 620 000 | 976 000 |
Tehát 1 000 000 szám sorbarendezése 1,4 másodperc, 10 000 000 elem sorbarendezése 20 másodperc alatt van, százmillió elemet bőven öt perc alatt rendez sorba, és háromszáz-millió elem sorba rakása is alig több, mint negyed óra a program számára. A program úgy van megírva, hogy a tömböt és a kupacot nettó egy példányban tárolja a memóriában, így n elem esetén durván egy érték mérete (4 bájt) szorozva n a program memóriahasználata (300M elem esetén 300 000 000 * 4 = 1 200 000 000 / 1 000 000 000 ≈ 1,2 GB)
A kód
A tényleges kód, amivel az előző program fut, alant megtekinthető. Az eleje és a vége csak C#-specifikus kód, az algoritmushoz valójában nem kell, de kattintásra megtekinthető.
using System;
namespace HeapSort
{
public class HeapSorter<T> where T : IComparable
{
// The array storing the heap and the sorted data (in this particular order)
private T[] array;
// The variable that defines the boundary between the heap and the sorted data
private int heapCount;
// optimization
private T swapTemp;
private bool isHeap = false;
public delegate void HeapCompleteEventHandler(HeapSorter<T> sender, int startIndex);
public event HeapCompleteEventHandler HeapComplete;
public HeapSorter(int length)
{
array = new T[length];
init();
}
private void init()
{
heapCount = array.Length;
HeapComplete += HeapSorter_HeapComplete;
}
void HeapSorter_HeapComplete(HeapSorter<T> sender, int startIndex) { }
private bool ascendingOrder = true;
public bool AscendingOrder
{
get { return ascendingOrder; }
set { ascendingOrder = value; }
}
public void QuickSort()
{
// Let's start with a heap
Heapify();
// For each element of the array
while (heapCount != 0)
{
/* We swap it with the last heap element and decrement the
* size of the heap, then reheapify the array */
swap(0, --heapCount);
Heapify(0);
}
}
public void Heapify()
{
// Heapify starting at the last element that may have children.
if (!isHeap)
Heapify(Convert.ToInt32(
Math.Floor(
((double)array.Length - 1.0) / 2.0 - 0.5
)
));
isHeap = true;
}
private void Heapify(int startWith)
{
/* We start checking the elemnets from (startWith) to 0 and sift
* them down as needed.*/
int i = startWith;
for (; 0 <= i; i--)
siftDown(i);
HeapComplete(this, startWith);
}
private void siftDown(int i)
{
// If the current item array[i] has a child, and
if (2 * i + 1 < heapCount)
{
// it has a second child too, and
if (2 * i + 2 < heapCount)
{
/* the second child is larger than the first child
* and also larger than the current item then
* we swap the current item with the second child.*/
if (isMoreExtreme(array[i], array[2 * i + 2]) &&
isMoreExtreme(array[2 * i + 1], array[2 * i + 2]))
{
swap(i, 2 * i + 2);
siftDown(2 * i + 2);
}
else
/* If there is a second child but the first child is larger
* than the current item, we swap with the first child.*/
if (isMoreExtreme(array[i], array[2 * i + 1]))
{
swap(i, 2 * i + 1);
siftDown(2 * i + 1);
}
}
else
/* If there is no second child, but the first child is larger
* than the current item, we swap with that. */
if (isMoreExtreme(array[i], array[2 * i + 1]))
{
swap(i, 2 * i + 1);
siftDown(2 * i + 1);
}
}
// Do nothing if the current item actually has the heap property
}
private void swap(int i, int p)
{
swapTemp = array[i];
array[i] = array[p];
array[p] = swapTemp;
isHeap = false;
}
private bool isMoreExtreme(T baseline, T obj)
{
if (ascendingOrder)
return baseline.CompareTo(obj) < 0;
else
return baseline.CompareTo(obj) > 0;
}
public T[] GetArray()
{
return array;
}
public int HeapLength
{
get
{
return heapCount;
}
}
public int SortedArrayLength
{
get
{
return array.Length - heapCount;
}
}
public T this[int index]
{
get
{
return array[index];
}
set
{
array[index] = value;
isHeap = false;
}
}
}
}