[SCRÂȘIT]
[FOȘTIT] [CLIC]
ERIK DEMAINE: Bine, bine ați
revenit la 006 Data Structures.
Astăzi, vom
acoperi un alt tip
de structură de date arborescentă
numită heap -- un heap binar.
Ne va permite să rezolvăm
problema de sortare într-un mod nou.
Permiteți-mi să vă reamintesc mai întâi
o parte:
problema pe care o vom
rezolva astăzi
se numește coadă de prioritate.
Aceasta este interfața.
Vom vedea mai multe
structuri de date,
dar o structură principală de date
pentru astăzi.
Și acesta este un subset
al interfeței setate.
Și subseturile sunt interesante
pentru că, potențial, le
putem rezolva mai bine,
mai rapid, mai simplu, ceva.
Și așa veți recunoaște...
ar trebui să recunoașteți
toate aceste operațiuni,
cu excepția faptului că în mod normal nu am
evidențiat operația maximă.
Deci, aici, suntem interesați
să stocăm o grămadă de articole.
Au chei pe care le
considerăm priorități.
Și dorim să putem
identifica elementul cu prioritate maximă
din setul nostru și să-l eliminăm.
Și așa că există o mulțime de
motivații pentru asta.
Poate aveți un router,
pachetele mergând în router.
Le sunt
atribuite priorități diferite.  Mai întâi
doriți să direcționați cea
mai mare prioritate.
Sau aveți procese
pe computer care încearcă
să ruleze pe un singur
thread-- single core
și trebuie să alegeți
pe care să rulați în continuare.
Și, de obicei, rulați
mai întâi procesele cu prioritate mai mare.
Sau încercați să simulați
un sistem în care evenimentele au loc
în momente diferite
și doriți să procesați
următorul eveniment ordonat în funcție de timp.
Toate acestea sunt exemple de
interfață de coadă prioritară.
Vom vedea chiar aplicații
din această clasă
când vom ajunge la algoritmi grafici.
Dar principalele două lucruri pe care
dorim să le putem susține
sunt inserarea unui articol,
care include o cheie,
și conducerea maximului
articolului și, de asemenea, returnarea acestuia
în același timp.  De
asemenea, vom vorbi despre
posibilitatea de a construi structura
mai rapid decât doar introducerea ei.
Dar, desigur, am
putea implementa
build pornind gol
și inserând în mod repetat.
Și, de asemenea, complexitatea
de a găsi doar max-ul
fără a-l șterge, asta ai
putea simula cu aceste două
operațiuni ștergând
max-ul și apoi reinserându-l,
ceea ce funcționează.
Dar, de multe ori, putem face mai repede.
Dar cele două operații principale
sunt inserarea și ștergerea max.
Și vom vedea câteva
structuri de date pentru a face acest lucru.
Ceva sugestii printre
structurile de date pe care le-am
văzut în această clasă?
Ce ar trebui să folosim pentru a rezolva
interfața de coadă prioritară?
Multe răspunsuri posibile.
PUBLIC: Secvență AVL?
ERIK DEMAINE: Secvența AVL?
Ooh, e interesant!
Sequence AVL este un răspuns bun,
dar poate versiunea mai fantezistă.
Da?
PUBLIC: Setați AVL?
ERIK DEMAINE: Setarea
AVL sună bine.
Set AVL acceptă aceste
operațiuni și multe altele.
Toate în log n timp, cu excepția
construirii, care durează n log n timp
pentru că trebuie să sortați mai întâi.
Deci setați AVL o
modalitate bună de a face acest lucru.
Vom reveni la
ideea dvs. de secvență AVL mai târziu.
Acest lucru primește log n pentru funcționare.
Grozav.
Adică, acesta este...
set AVL este cea mai
puternică structură de date a noastră.
Face toate operațiunile la care ne pasă
pe partea setată.
Și secvența AVL
face toate operațiunile
din partea secvenței.
Dar rețineți că acesta este
un set, nu o secvență.
Ne pasă de chei.
Există hackuri pentru a ocoli
asta cu secvențe AVL,
dar hai să facem asta mai târziu.
Atât de grozav, dacă am vrea
, de exemplu, să
accelerăm find_max într-un set AVL.
Am putea adăuga mărire.  Ne-am
putea... ne amintim de
mărirea proprietăților subarboarelor?
Putem folosi asta pentru a obține un
timp constant find_max
prin stocarea în fiecare nod a
elementului cheie maxim
din subarborele.
Și aceasta este o proprietate subarbore.
Este unul despre care am
menționat ultima clasă.
Așa că am putea chiar să îmbunătățim
asta pentru a reduce ceva timp.
Grozav.
Deci am terminat.
Sfârșitul prelegerii.
[Chicote] Într-un anumit
sens, este adevărat.
Dar ceea ce vom
vedea astăzi
este o altă structură de date
numită heap binar,
care este, într-un anumit sens, o
simplificare a setului AVL.
Realizează practic
aceleași limite de timp.
Construirea va fi mai rapidă
cu un factor de jurnal.
Dar nu acesta este
motivul principal pentru care ne pasă de ei.
Principalul avantaj este
că sunt mai simple
și ne oferă un
algoritm de sortare în loc.
Deci am aici
trei dintre operațiunile despre care am
vorbit --
build, insert și delete_max.
Deci am setat arbori AVL acolo -
n log n build, log n insert,
log n delete.
Deci, pe drumul către grămada noastră,
vreau să menționez alte două
structuri de date.
Unul este o matrice dinamică,
dar nesortată.
Iar celălalt este un
tablou sortat dinamic.
Acestea sunt structuri de date mai simple

despre care am vorbit de
multe ori înainte.
Și sunt un fel
de motivații utile pentru
început, pentru că o grămadă va
fi construită deasupra matricelor
în loc de-- ei
bine, este un fel de fuziune
între matrice și arbori.
Deci, dacă am o
matrice nesortată, aceasta este foarte ușor
de inserat, nu?
Doar atasez la final.
Aceasta este ceea ce am
numit inserare ultima.
Așa că inserția este rapidă,
amortizată constant.  S-
ar putea să trebuiască să
redimensionăm matricea,
dar asta este
partea amortizată.
Dar ștergerea maximă este lentă.
Într-o matrice nesortată, nu
știu unde este maximul.
Așa că trebuie să scanez
întreaga matrice.
Așa că scanez prin
matrice, identific
că maximul este undeva
la mijloc și apoi,
dacă vreau să-l șterg,
vreau să șterg acel
element maxim, ei bine,
într-o matrice dinamică,
tot ce pot face
este să șterg.  ultimul
element eficient.
Așa că aș putea, de exemplu, să-
l schimb cu ultimul element.
Așa că iau acest element
și îl pun aici, apoi
șterg ultimul element din acea
matrice, care este pop în Python
sau delete_last în lumea noastră.
Deci, în general, acesta este
timp liniar, ceea ce este rău.
Dar am vrut să evidențiez
exact cum se
face pentru un motiv la care vom
ajunge într-o clipă.  O
matrice sortată este un
fel invers.
Este foarte ușor să găsești max.
Unde este?
La sfârșitul.
delete_max, elementul maxim
este întotdeauna ultimul element
dintr-o matrice sortată crescândă.
Bănuiesc că este
amortizat constant, pentru că atunci
trebuie să îl șterg, ceea ce
poate duce la redimensionare.
Inserarea, totuși, va
fi liniară,
pentru că poate pot
căuta binară pentru a găsi
unde aparține elementul adăugat.  Să
presupunem că tocmai am
adăugat acest articol aici.
Aș putea
căuta binară pentru a-l găsi,
dar apoi va
trebui să fac o schimbare mare.
Așa că aș putea la fel de bine
să schimb în mod repetat
până când găsesc poziția
în care aparține elementul adăugat x.
Și acum am restabilit
ordinea sortată.
Asta necesită
timp liniar, ceea ce este rău.
Și ceea ce ne dorim este cumva cel
mai bun dintre aceste două lumi.
Inserarea este rapidă pentru matrice.
Ștergerea este rapidă pentru
o matrice sortată.
Nu putem obține
timp constant pentru amândoi.
Dar putem obține
timp de înregistrare pentru ambele.
Știm deja cum
cu arbori AVL setați.
Dar vom vedea un
alt mod de a face asta astăzi.
Și principala motivație pentru
un alt mod de a face acest lucru
este sortarea.
Așa că vreau să definesc o
sortare prioritară în coadă.
Deci, având în vedere orice structură de date
care implementează o interfață de coadă prioritară
, în special
insert și delete_max,
pot crea un algoritm de sortare.
Ce trebuie să fac?
Inserați toate elementele,
ștergeți toate elementele.
Dar pentru că atunci când le șterg,
ies mai întâi cele mai mari,
le primesc în
ordine inversă.
Apoi aș putea inversa în
timp liniar și mi-am sortat articolele.
Deci putem introduce (x) pentru
x în A, sau (build(A)),
și apoi șterge_max în mod repetat.
Cât timp
durează acest algoritm?
Am de gând să introduc
câteva notații aici.
Oricât de mult este nevoie
pentru a construi n articole,
numiți acea T sub build (n) plus--
scuze-- plus de n ori
timpul pentru a face o ștergere_max.
Sau putem scrie
acest lucru ca de n ori timp
pentru a face o inserare, plus
timp pentru a face o ștergere_max.
Așadar, folosesc aceste funcții T
pentru a abstractiza care sunt
timpii de rulare furnizați
de structura mea de date care
implementează această interfață.
Interfața spune că
ceea ce este corect este,
iar aceste funcții T
îmi oferă limite de performanță.
Deci, dacă conectez fiecare dintre
aceste structuri de date,
primesc un algoritm de sortare.
Primesc sortarea AVL,
sortarea matricei,
sortarea matricei asortate.
Cum arată acelea?  Se
pare că multe dintre
acestea sunt familiare.
Deci, setați AVL-urile iau
log n per operație.
Deci obținem un algoritm de sortare n log n
din ele, care
este inserarea tuturor
elementelor în arborele AVL.
Nu vreau să folosesc AVL build,
deoarece aceasta folosește sortarea și nu este
permisă sortarea
pentru a implementa sortarea.
Dar am văzut cum să
introducem într-un arbore AVL
și să menținem chestia echilibrată.
Deci ia log n fiecare.
Și apoi putem găsi
maximul, îl ștergem, reechilibram
și așa mai departe.
Timpul total va fi n log n.
Acesta este un algoritm pe care îl
numim sortare AVL.
Este un pic complicat, deoarece
arborii AVL sunt complicati.
Dar ne oferă o
comparație optimă și log n.
Acum, cum rămâne cu sortarea matricei?  Deci, să
presupunem că folosesc
o matrice nesortată.
Inserez articolul.
Deci, dacă inserez elementele...
deci fac toate inserările
aici înainte de toate ștergerile.
Deci, ceea ce se va întâmpla
este să inserez elementele
în ordinea originală a matricei.
Cu alte cuvinte,
doar iau matricea.
Și apoi ceea ce fac este să
extrag în mod repetat elementul maxim
căutându-l, mutându-
l la sfârșitul matricei
și apoi repetând acel proces.
Sună cunoscut?
Acesta este un fel de selecție
din cursul trei.
Deci, aceasta-- matricele
ne oferă sortarea de selecție.
Acesta este un nou mod
de a ne gândi la ceea ce
făceam pe atunci.
Cu o matrice sortată,
ce facem?
Inserăm toate elementele.
Acolo se întâmplă de fapt toată
munca, pentru că
menținem matricea sortată.
Deci începem cu o matrice goală.
Este sortat.
Adăugăm un articol.
OK, încă este sortat.
Adăugăm un al doilea
articol și schimbăm
dacă este nevoie pentru a sorta.
În general, când adăugăm un
articol, îl schimbăm spre stânga
până când este sortat din nou.
Acesta este un fel de inserție.
Un fel de cool, acesta este un
cadru unificator pentru trei
algoritmi de sortare pe care i-am văzut înainte.
De fapt nu am vorbit
despre sortarea AVL data trecută,
dar era în note.
Și aceasta este
partea dreaptă a acestui tabel.
Deci, desigur, aceste structuri de date matrice
nu sunt eficiente.
Acestea necesită timp liniar pentru
unele operații.
Deci algoritmii de sortare
nu sunt eficienți.
Dar sunt cei pe care i-am
mai văzut,
așa că este bine să vedem
cum se potrivesc aici.  Au
avut...
sortarea de selecție și
sortarea de inserție aveau avantajul
că erau la locul lor.  Aveai
nevoie doar de un
număr constant de pointeri sau indici
dincolo de matrice în sine.
Deci sunt foarte eficiente în spațiu.
Deci asta a fost un plus pentru ei.
Dar au nevoie de n
timp la pătrat, așa că nu ar trebui să
le folosiți niciodată, cu excepția n,
cel mult, 100 sau ceva de genul.
Sortarea arborelui AVL este grozavă și apoi
devine n log n timp, probabil
mai complicat decât
sortarea de îmbinare și ați
putea rămâne la sortarea de îmbinare.
Dar nici sortarea de îmbinare, nici
sortarea de arbore AVL nu sunt în vigoare.
Așadar, scopul
de astăzi este de a obține tot ce este
mai bun din toate acele
lumi în sortare
pentru a obține n log n
comparații, ceea ce
este optim în
modelul de comparație,
dar să fie în loc.
Și asta vom
obține cu grămezi binare.
Vom proiecta
o structură de date care
se întâmplă să se construiască
puțin mai rapid - așa cum am menționat,
construirea liniară a timpului.
Deci nu reprezintă o
ordine sortată în același mod în
care sunt arborii AVL.
Dar va fi un
fel de arbore.  De
asemenea, va fi bazat pe matrice.
Vom obține
timp logaritmic pentru insert și delete_max.  Se
întâmplă să fie amortizat,
pentru că folosim matrice.
Dar lucrul cheie este că este
o structură de date în loc.
Este format doar dintr-o
serie de elemente.
Și așa, atunci când îl conectăm
la algoritmul nostru de sortare -
sortarea în coadă cu prioritate sau
algoritmul de sortare generic -
nu numai că obținem
performanță n log n,
dar obținem și un
algoritm de sortare la loc.
Acesta va fi primul
și singurul nostru -- din această clasă --
n log n
algoritm de sortare pe loc.
Misto.
Acesta este scopul.
Hai să o facem.
Deci, ce vom face,
pentru că suntem la locul lor,
practic trebuie să avem o
matrice care să stocheze articolele noastre finale.
Aceasta este un fel de
definiție a in-place,
folosind doar n sloturi
de memorie exact de
dimensiunea numărului de
elemente din structura noastră.
Dar, evident, nu vom
folosi o matrice obișnuită nesortată
sau o matrice obișnuită sortată.
Vom folosi
matrice ca un fel
de tehnologie de bază
pentru modul în care sunt stocate lucrurile.
Dar ne-am dori foarte mult
performanța logaritmică, care
ar trebui să te facă să te gândești la arbore.
Singura modalitate de a obține un jurnal este
arborele binar, mai mult sau mai puțin.
Deci, cumva, vrem să
încorporam un arbore într-o matrice.
Lasă-mă să iau un exemplu.
Lasă-mă să desenez un copac.
Dacă ar trebui să aleg
orice copac bătrân pe care vreau,
aș alege un copac care este
în principiu perfect echilibrat.
Perfect echilibrat ar
fi așa, unde...
care este proprietatea?
Că am toate
aceste niveluri...
toate aceste adâncimi sunt
complet pline de noduri.
Aceasta este adâncimea 0.
Amintiți-vă, aceasta este adâncimea 1, aceasta
este adâncimea 2, aceasta este adâncimea 3.
Deci, ceea ce mi-aș dori cu adevărat
este să am 2 la
nodurile i la adâncimea i.
Acesta ar fi un
arbore binar perfect.
Dar asta funcționează doar când n este 1
mai mic decât o putere a lui 2, nu?
Nu pot realiza întotdeauna
asta pentru orice n.
Și astfel, cel mai bun
lucru pe care l-aș putea spera
este 2 la i la
nodurile de la adâncimea i
până la ultima
i-- cea mai mare adâncime.
Și la acel nivel, încă voi
restricționa lucrurile.
Voi forța
toate nodurile
să fie cât mai departe posibil.
Așa că vreau să spun, cu excepția
adâncimii maxime unde sunt nodurile --
le voi numi justificate la stânga.
Și aceste două
proprietăți împreună
este ceea ce eu numesc un
arbore binar complet.
De ce este asta interesant?
Pentru că susțin că pot reprezenta
un arbore ca acesta ca o matrice.
Am restrâns lucrurile destul de mult
încât să pot desena o matrice
aici.
Și ceea ce voi
face este să scriu aceste noduri
în ordine de profunzime.
Așa că scriu mai întâi A,
pentru că acesta este pasul 0.
Apoi B, C, acesta este pasul 1.
Apoi, ei bine, sunt
alfabetice.
Am făcut-o așa.
D, E, F, G este adâncimea 2.
Și apoi H, I, J este pasul 3.
Acesta este foarte diferit de
ordinea de traversare a unui arbore.
Ordinea transversală ar fi
fost H, D, I, B, J, E, A, F, C,
G, OK?
Dar aceasta este ceea ce am
putea numi ordinea adâncimii,
faceți
mai întâi nodurile cu cea mai mică adâncime - un
mod foarte diferit de a aranja lucrurile
sau de a ne linealiza datele.
Și așa
va arăta o grămadă.
Deci, lucrul minunat este că
între arbori binari completi
și matrice este o bijecție.
Pentru fiecare matrice, există un
arbore binar complet unic.
Și pentru fiecare arbore binar complet
, există o matrice unică.
De ce?
Pentru că
constrângerea completă forțează
totul... îmi forțează mâna.
Există doar... dacă
vă dau un număr n,
există o
formă de copac de mărimea n, nu?
Doar completați
nodurile de sus în jos până
ajungeți la ultimul nivel.
Și apoi trebuie să
le completați de la stânga la dreapta.
Este ceea ce ați putea numi
ordine de citire pentru notarea nodurilor.
Și matricea
vă spune ce taste merg unde.
Acesta este primul nod pe care îl
scrieți la rădăcină,
acesta este următorul
nod pe care îl scrieți
la copilul din stânga al
rădăcinii și așa mai departe.
Deci aici avem un
arbore binar reprezentat ca o matrice,
sau o matrice care reprezintă
un arbore binar.

Arborele binar foarte specific,
are un avantaj clar, care
este echilibrul garantat.
Nu sunt necesare rotații în grămezi,
deoarece arborii binari completi
sunt întotdeauna echilibrați.
De fapt, au cea mai bună
înălțime posibilă,
adică tavanul de buștean n.
Echilibrat, amintește-ți,
însemna doar că ești mare O de buștean n.
Acesta este de 1 ori log n.
Deci este cel mai bun nivel de
echilibru la care ai putea spera.
Deci cumva, susțin, putem
menține un arbore binar complet
pentru rezolvarea cozilor de prioritate.
Acest lucru nu ar fi
posibil dacă ați
încerca să rezolvați
întreaga interfață setată.
Și acesta este un fel de
lucru genial despre grămezi,
este că concentrându-ne doar pe
subsetul interfeței setului,
putem face mai mult.
Putem menține această
proprietate foarte puternică.
Și pentru că avem această
proprietate foarte puternică,
nici nu trebuie
să depozităm acest copac.
Nu vom stoca
pointerii stânga și dreapta și
pointerii părinte, doar vom
stoca matricea.
Aceasta este ceea ce numim o
structură de date implicită, ceea ce
înseamnă practic niciun pointer,
doar o matrice de n elemente.
Cum vom scăpa
fără a stoca indicatoare?  Tot
mi-ar plăcea să-l
tratez ca pe un copac.
Încă aș vrea să știu că
copilul stâng al lui B este D
și copilul din dreapta B este E.
Vom vedea de ce într-o clipă.  Ei
bine, putem face asta
cu aritmetica indexului.
Deci poate ar trebui să adaug niște
etichete înainte de a ajunge acolo.
Deci, această matrice
are în mod natural indici.
Acesta este indexul 0.
Acesta este indexul 1, indexul 2, indexul
3, indexul 4, indexul 5, indexul 6, 7
, 8, 9, pentru că
există 10 articole, de la 0 la 9.
Și pot aplica acele
etichete aici, sus,  de asemenea.
Acestea sunt aceleași
noduri, deci 0, 1, 2.
Acesta este doar o ordine de adâncime.
Dar odată ce voi avea
această etichetare, va
fi mult mai ușor să-mi dau seama
.
Deci, dacă aș vrea să știu că
copilul din stânga al lui B este D,
cumva, având în vedere numărul 1,
vreau să calculez numărul 3.
Adăugați 2, există tot
felul -- înmulțiți cu 3,
există tot
felul de operații
care necesită  1 și transformați-l în 3.
Dar există doar unul care va
funcționa în toate cazurile.
Iar intuiția aici
este, ei bine, trebuie să 2
nodurile i la nivelul i.
Dacă vreau să merg la
nivelul copil,
există 2 la nodurile i plus
1 acolo jos --
exact dublu.
Deci este ultimul,
dar asta nu va conta cu adevărat.
Dacă există un copil lăsat,
se va comporta la fel.
Și astfel, intuitiv, am
acest spațiu de dimensiunea 2 la i.
Trebuie să-l extind la un spațiu
de dimensiunea 2 la i plus 1,
deci ar trebui să înmulțesc cu 2.
Și este aproape corect, dar
apoi există niște constante.
Asa ca as vrea sa spun de 2 ori i.
Dar dacă ne uităm la
exemplele de aici, 1 ori 2
este 2, care este 1 mai mic decât 3. De
2 ori 2 este 4, care
este 1 mai mic decât 5.
Hei, aproape că am înțeles bine.
Este doar cu 1.
Off cu 1 este--
erorile de index sunt cele mai comune
lucruri în informatică.
Dar copilul potrivit?
Dacă copilul stâng este un 2i plus
1, unde este copilul drept?
Aud o mulțime de mormăituri.
2i plus 2-- încă unul.
Pentru că scriem lucrurile de la
stânga la dreapta în ordine profundă,
copilul din dreapta este
fratele drept al celui stâng.
Deci este doar unul mai mare, bine?
Având în vedere aceste reguli,
putem calcula și părinte.
Este orice
este inversul
ambelor
funcții, pe care vreau
să le împart la 2 la un moment dat.
Vreau să mă întorc la i dat
2i plus 1 sau dat 2i plus 2.
Și deci, dacă scad 1
din i, atunci primesc fie
2i, fie 2i plus 1.
Și apoi, dacă iau o
împărțire întreagă cu 2, obțin  i--
originalul i.  Îmi
pare rău, poate voi numi
asta j pentru a fi mai clar.
Deci j este copilul stâng sau drept.
Apoi pot să reconstruiesc
eu, care era părintele.
Deci, acestea sunt
operații aritmetice cu numere constante.
Deci nu trebuie să stochez
indicatori la stânga și la dreapta.
Pot să le calculez
oricând am nevoie de ele.
Ori de câte ori mă aflu la
un nod ca E
și vreau să știu
care este copilul său stâng -
îmi pare rău, având în vedere
indexul nodului 4, care
se întâmplă să conține
elementul E și
vreau să știu care este copilul său stâng
, doar înmulțesc  cu 2
și adăugați 1.
Obțin 9.
Și apoi, pot indexa în
această matrice la poziția 9.
Pentru că nu-- asta este
doar în capul meu, amintiți-vă.  Ne
gândim doar că
aici este un copac.
Dar, în realitate, pe computer,
există doar matricea.
Deci, dacă vrem să trecem de la E
la J, putem, de la 4 la 9.
Dacă mergem să încercăm să mergem la
copilul potrivit, înmulțim cu 2.
8 adunăm 2-- 10.
Și vedem, o, 10 este
dincolo de sfârșitul matricei.
Dar matricea noastră își stochează
dimensiunea, așa că ne dăm seama, oh, E
nu are un copil potrivit.
Acesta este ceva ce poți
face doar într-un arbore binar complet.
Într-un arbore binar general
nu
aveți aceste proprietăți frumoase.
Cool, deci acesta este
practic o grămadă.
Trebuie doar să
mai adaug o proprietate,
numită în mod natural
proprietatea heap.
Deci, există mai multe
tipuri de grămezi.
Acest tip de heap se
numește heap binar.
Vom vorbi despre alții
în prelegerile viitoare.  Îi voi
numi
Q. Lucru explicit--
acesta este o matrice care reprezintă
un arbore binar complet,
numit matrice Q. Și
dorim ca fiecare nod să satisfacă
așa-numita proprietate max-heap,
care spune Q[i]  este mai mare
sau egal cu Q[j] pentru ambii
copii din stânga lui i și din dreapta
lui i.
Deci avem un nod i.
Și are doi copii --
2i plus 1 și 2i plus 2.
Acestea sunt două valori ale lui j.
Ceea ce ne dorim este o relație
mai mare decât sau egală
aici și aici.
Deci acest nod ar trebui să fie
mai mare atât decât acesta, cât
și decât acesta.
Care dintre acestea este mai mare?
Nu știm și
nu ne pasă -
foarte diferit de
arbori binari de căutare
sau arbori binari setați, unde am
spus că acești tipi sunt mai mici
sau egali cu acesta,
acesta era mai mic
sau egal cu toate nodurile
în subarborele de aici.
Spunem doar local
, acest nod
este mai mare sau egal
cu acest nod și acest nod.
Deci cel mai mare este în vârf.
Așa că o lemă drăguță despre
aceste grămezi... e ciudat.
Lasă-mă să-ți dau
mai multă intuiție.
Dacă sunteți un heap binar, dacă
îndepliniți această proprietate max-heap
peste tot, atunci
de fapt, veți afla
că fiecare nod i este mai mare
sau egal cu toate nodurile
din subarborele său.
Aceștia sunt ceea ce numim
descendenți în subarborele lui i.  Să
mă uit la acest exemplu.
Deci nu am scris
niciun număr aici.
Iti poti imagina.
Deci A aici este mai mare
sau egal cu B și C
și B este mai mare
sau egal cu D și E
și C este mai mare
sau egal cu F și G,
D este mai mare sau
egal cu H și I și
E este mai mare
sau egal cu J.
Aceasta ar face din această
structură o grămadă,
nu doar un arbore binar complet.
Deci, ce înseamnă asta?
Aceasta implică faptul că A
trebuie să fie maximul.
Deci vă uitați la orice
nod aici, cum ar fi J, A
este mai mare sau egal cu B
este mai mare sau egal cu E
este mai mare sau egal cu
J. Și, în general, ceea ce
spunem este că A este mai mare
decât sau  egal cu toate nodurile
din arbore.
B este mai mare sau egal
cu toate nodurile din subarborele său de
aici.
C este mai mare sau egal
cu toate nodurile din subarborele său.
Asta
spune această lemă.
Puteți demonstra această
lemă prin inducție.
Dar este chiar simplu.
Dacă aveți două noduri, i
și j, iar j este undeva
în subarbore,
înseamnă că există
o cale descendentă de la i la j.
Și știți că,
pentru fiecare margine pe care o
traversăm pe o
cale descendentă, cheia noastră
coboară în mod non-strict.
Deci fiecare copil este mai mic
sau egal cu părintele său.
i este mai mare
sau egal cu acesta,
este mai mare sau
egal cu acesta,
este mai mare sau
egal cu acesta,
este mai mare sau
egal cu j, OK?
Deci, prin tranzitivitatea
mai mică sau egală cu,
știți că i este, de fapt,
mai mare sau egal cu j.
Sau scuze, cheia
din i este mai mare
sau egală cu cheia din j.
Acesta este ceea ce
numim i, indexul.
Acesta este ceea ce am
numi Q din i.
Acesta este indicele j Q din j.  Un
mod foarte diferit de a
organiza cheile într-un arbore,
dar după cum vă puteți
imagina, acest lucru va
fi bun pentru cozile prioritare.
Pentru că
cozile prioritare trebuie doar
să găsească elementele maxime.
Apoi trebuie să-l ștergă.  Va
fi mai greu,
pentru că conducerea rădăcinii
este, ca... acesta este cel mai greu
nod de șters, intuitiv.
Chiar prefer
să șterg frunzele.
Dar conducerea frunzelor și
păstrarea unui arbore binar complet
este de fapt destul de dificilă.
Dacă vreau să șterg
H, acesta nu
arată ca un
arbore binar sau nu mai
arată ca un
arbore binar complet.
Nu este lasat justificat.  În
mod similar, dacă vreau să
șterg F, este rău.
Pentru că acum, nu
am patru noduri aici.
Singurul nod care este ușor
de șters este J, nu?
Dacă elimin acel nod,
mai am un arbore complet.
Ultima frunză, ultima
poziție din matricea mea,
este cea care este
ușor de șters.
Asta e bine, pentru că matricele sunt
bune la conducerea ultimului element.
Dar ceea ce am setat aici este că
este ușor să găsești max.  Va
fi
aici sus, la rădăcină.
Ștergerea lui este enervantă.  Aș
dori cumva să iau acea
cheie și să o pun la poziția--
la ultima poziție
la ultima frunză,
pentru că aceasta este cea
care este ușor de șters.
Și asta este într-adevăr
ceea ce vom
face într-un algoritm de ștergere.
Lasă-mă mai întâi să inserez.
Cred că este puțin
mai simplu, cam simetric
față de ceea ce tocmai am spus.
Deci, dacă vreau să inserez o cheie sau
un element x care are o cheie,
din nou, singurul lucru pe care îl
pot face într-adevăr într-o matrice --
dacă vreau să adaug un element nou,
trebuie să ajungă la sfârșit.
Singurul lucru pe care
știm să facem este
să inserăm la sfârșitul unui tablou.
Aceasta este ceea ce am
numit insert_last.
acest?
Corespunde cu adăugarea
unui nod care conține x--
elementul x-- în ultimul
nivel al arborelui binar complet
.
Fie merge în dreapta
tuturor nodurilor existente,
fie începe un nou nivel.
Dar va fi întotdeauna
ultima frunză.
După ce facem
inserarea, acesta va fi
la dimensiunea poziției Q minus 1.
Acest lucru probabil
nu este suficient, totuși.
Tocmai am inserat un
element arbitrar într-o frunză.
Și acum, este posibil să nu mai satisfacă
proprietatea max-heap.
Așa că haideți să verificăm dacă da,
iar dacă nu, remediați.
Asta stim sa facem.
Dar de data aceasta, nici
măcar nu vom avea
nevoie de rotații,
ceea ce este mișto.
Deci voi defini
o operațiune numită
max_heapify_up.
Acest lucru va face lucrurile
mai mult ca o grămadă maximă.
Vom începe de la dimensiunea
Q minus 1 pentru valoarea noastră i.
Dar va fi recursiv,
așa că ceea ce vom face
este să privim un nod i,
în special cel
care tocmai a fost inserat.
Și unde ar putea
încălca lucrurile?
Ei bine, cu părintele lui, pentru că
habar n-avem ce cheie
tocmai am pus aici.
Poate că este mai puțin decât părintele nostru.
Atunci suntem fericiți.
Dar dacă este mai mare decât
părintele nostru, avem probleme
și ar trebui să o reparăm.
Deci, dacă elementul din
cheia părintelui este mai mic decât cheia i--
ah, văd că am uitat să scriu
cheia și toate aceste puncte.
Aceasta ar trebui să fie
cheia punct și cheia punct,
deoarece Q[i] este un
element care își primește cheia.
Deci acesta este cazul prost.
Asta dacă părintele este
mai mic decât copilul.
Ne-am dorit ca părintele
să fie întotdeauna mai mare
sau egal cu copiii săi.
Deci, în acest caz,
ce am putea face?
Schimbați-le.  Să
schimbăm Q părintele lui i--
excelent, mai mult
cretă-- cu Q[i].
Acum sunt în ordinea corectă.
Acum, trebuie să ne gândim
ce se întâmplă cu celălalt copil
al acelui nod?
Și cum rămâne cu părintele lui?
Deci am niște numere aici.  Să
spunem că acesta a fost
5 și acesta a fost 10.
Ce știu despre
această imagine înainte?  Ei
bine, știu că 10 este
acest articol nou introdus.
Este singurul care
ar fi putut cauza încălcări
atunci când l-am introdus prima dată.
Așa că știu că înainte de asta--
înainte să mă mișc cu 10,
știam că toate lucrurile
din acest subarboresc din stânga
sunt mai mici sau egale cu
5, și toate cele de aici de sus
sunt create egale cu 5.
Știu, de asemenea, că nodurile de
aici,  de fapt, au fost mai mici
sau egale cu 5.
În afară de acest nod 10 pe
care tocmai l-am inserat,
acesta a fost un heap corect.
Deci 5 a fost un separator între--
lucrurile de deasupra lui pe
lanțul strămoși
sunt mai mari sau egale cu
5, iar lucrurile din subarborele său
sunt mai mici sau egale cu acesta.
Deci, după ce fac acest schimb, pe
care doar îl voi face...
după ce schimb elementele 5 și
10, 10 este aici sus, 5 este aici.
Și acum, îmi dau seama,
OK, grozav, această margine
este fericită, pentru că acum 10 este
mai mare sau egal cu 5.
Dar și această margine este fericită,
pentru că odinioară era fericit
și i-am făcut doar
părintele mai mare.
Acum această margine poate este proastă.
Și deci trebuie să recurgem--
recurs pe părinte.
Dar asta e tot.
Așa că am reparat această margine.
Inițial, acest lucru se întâmplă
în jos, la frunză.
Dar, în general,
luăm articolul pe
care l-am inserat, care este x,
și începe de la ultima frunză
și poate fi
bule pentru o perioadă.
Și poate ajunge până la
rădăcină
dacă am inserat un
nou element maxim.
Dar la fiecare treaptă
urcă câte una.
Și astfel,
timpul de rulare al tuturor acestor lucruri
este înălțimea
copacului, care este jurnalul n.
Și pentru că există doar acest
element care ar putea
fi greșit, dacă se
oprește vreodată să se miște,
tocmai am verificat
dacă îndeplinește
proprietatea max-heap.
Dacă ajunge la
rădăcină, puteți
verifica și dacă îndeplinește
proprietatea max-heap.
Deci, există un caz de bază pe care
nu l-am scris aici, și
anume dacă i este egal cu 0, suntem
la rădăcină, am terminat.
Și apoi puteți dovedi
acest lucru corect prin inducție.
Există doar un articol care este
în locul greșit, inițial.
Și l-am pus în locul potrivit.
Există multe locuri în care ar putea
merge, dar o vom muta în,
cred, poziția unică a strămoșului,
care este corectă--
care satisface
proprietatea maxim-heap, OK?
Deci asta este inserarea.
Delete va fi aproape la
fel, delete_min, adică...
scuze, delete_max, mulțumesc.
Desigur, puteți defini
toate aceste lucruri
pentru min în loc de max.
Totul funcționează la fel.
Îmi este greu să-mi
amintesc pe care o
facem.
Doar nu comuta, nu poți folosi
un max-heap pentru a face delete_min.
Nu puteți folosi un min-heap
pentru a face delete_max,
dar puteți folosi un
min-heap pentru a face delete_min.  Asta e
bine.
Așadar, așa cum am spus, singurul nod pe care
știm cu adevărat cum să îl ștergem
este ultima frunză
de la ultimul nivel,
care este sfârșitul matricei.
Pentru că asta e ceea ce matricele
pot șterge eficient.
Și ceea ce trebuie să
ștergem este elementul rădăcină,
pentru că acesta este întotdeauna
cel maxim, care
se află la prima
poziție în matrice.
Deci ce facem?
Schimbă-le, trucul nostru obișnuit.
Cred că cel mai tare
lucru la grămezi
este că nu trebuie
să facem niciodată rotații.  Vom
face doar
schimburi, ceea ce am
avut de-a face și cu copacii --
copacii binari.
Q[0] cu Q din ultimul articol--
grozav, gata.
Acum avem ultimul element pe care
vrem să-l ștergem.
Deci ștergem_last, sau introducem în
Python, și boom, avem...
acum am șters
elementul maxim.
Desigur, este posibil să fi
încurcat și proprietatea max-heap,
așa cum am făcut cu insert.
Deci, cu inserție, am
adăugat o ultimă frunză.
Acum, ceea ce facem este să
schimbăm ultima frunză
cu...
Arăt spre
imaginea greșită.
Lasă-mă să mă întorc la acest copac.
Ceea ce am făcut a fost să schimbăm elementul J
cu A. Deci problema este acum...
și apoi am șters acest nod.
Problema este acum
că acel nod rădăcină
are poate o cheie foarte mică.
Pentru că cheia care este aici
acum este orice era aici jos,
care este foarte jos în copac.
Deci intuitiv,
aceasta este o valoare mică.
Aceasta ar trebui să
fie valoarea maximă
și am pus doar o
valoare mică în rădăcină.
Deci ce facem?
Heapify jos.  Vom
lua acel
element și îl vom împinge cumva în
jos până în copac până când...
jos în copac până când
proprietatea maxim-heap este satisfăcută.
Deci, acesta va
fi max_heapify_down.
Și vom începe de la poziția
0, care este rădăcina.
Și max_heapify_down va
fi un algoritm recursiv.
Deci vom începe de la o
anumită poziție i.
Și inițial, aceasta este rădăcina.
Și ceea ce vom face este să ne
uităm la poziția I și la cei doi
copii ai săi.
Deci, să presupunem că punem o
valoare foarte mică aici, cum ar fi 0.
Și să presupunem că avem
copiii noștri, 5 și 10.
Nu știm, poate le
voi schimba ordinea doar
pentru a fi mai generic, pentru că
arată  ca nu chiar
un arbore de căutare binar
, dar nu
știm ordinea lor relativă.
Dar unul dintre ele este mai mare
sau egal cu celălalt
într-o anumită ordine.
Și ce aș vrea să
fac pentru a remedia această imagine locală?
Da, vreau să schimb.
Și aș putea schimba--
0 este în mod clar în locul greșit.
Trebuie să coboare
mai jos în copac.
Pot schimba 0 cu
5 sau 0 cu 10.
Care dintre ele?
10.
Aș putea desena poza cu
5, dar nu va fi fericit.
De ce 10?
Vrem să o facem
cu cea mai mare,
pentru că atunci această
margine va fi fericită
și, de asemenea, această margine
va fi fericită.
Dacă aș schimba 5 acolo sus,
marginea 5/10 ar fi nefericită.  Nu ar
satisface
proprietatea max-heap.
Așa că pot face o schimbare și pot
repara proprietatea max-heap.
Cu excepția faptului că, din nou, 0 poate fi
nemulțumit de copiii săi.
0 a fost acest articol care
a fost în locul greșit.
Și așa a făcut-o să
meargă mai jos.
Dar 5 vor fi...
5 nici nu s-au mișcat.
Deci e fericit.
Totul în acest
subarbore este bun.
Dar părintele?  Ei
bine, dacă vă gândiți
bine, pentru că totul
a fost un heap corect
înainte de a adăuga 0
sau înainte de a pune 0 prea
sus, toate aceste noduri
vor fi mai mari sau egale
cu 10 pe calea strămoșilor.
Și toate aceste noduri au fost
mai mici sau egale cu 10
înainte, cu excepția cazului în care
sunteți egal cu 5.
Deci, asta este încă adevărat.
Dar vezi tu, acest copac este fericit.
Acest copac poate fi încă nefericit.
0 ar putea avea nevoie
să împingă mai departe.
Asta va
fi recursiunea.
Așa că verificăm aici.
Există un caz de bază, adică
dacă i este o frunză, am terminat.
Pentru că nu e
nimic sub ele.
Așa că satisfacem
proprietatea max-heap la i
pentru că nu există copii.
Altfel, să ne uităm la
frunza din stânga--
scuze, stânga nu frunză--
dintre cei doi copii din
stânga și dreapta lui i.
Corect dacă s-ar putea să nu exist.
Atunci ignoră-l.
Dar printre cei doi
copii care există,
găsiți-l pe cel care are
valoarea maximă a cheii, Q[j].key.  A
fost 10 în exemplul nostru.
Și atunci, dacă aceste
articole nu sunt în ordine,
dacă nu vom satisface...
atât de mai mare decât
ar fi satisfăcut.
Mai puțin decât Q[j] ar fi
opusul proprietății max-heap
aici.
Dacă proprietatea max-heap
este încălcată,
atunci o rezolvăm
schimbând Q[i] cu Q[j],
apoi recurgem pe j--
apelăm max_heapify_down de j.
Asta este.  Deci destul de
simetric.
Inserarea a fost puțin
mai simplă, pentru că
avem un singur părinte.
Delete_min, pentru că
împingem în jos,
avem doi copii.
Trebuie să alegem unul.
Dar există o
alegere clară, cea mai mare.
Și din nou, acest algoritm--
toată chestia asta--
va lua ordinul h timp,
înălțimea arborelui,
care este log n, pentru că
nodul nostru doar bule în jos.
La un moment dat, se oprește.
Când se oprește, știm că
proprietatea max-heap
a fost satisfăcută acolo.
Și dacă verificați pe
parcurs, prin inducție,
toate celelalte
proprietăți max-heap
vor fi satisfăcute,
pentru că erau înainte.
Deci aproape forțat ce
am putea face aici.
Lucrul uimitor este
că puteți menține de fapt
un
arbore binar complet care satisface
proprietatea max-heap.
Dar odată ce ți se spune asta,
algoritmul cade.
Pentru că avem o matrice.
Singurul lucru pe care îl putem
face este să inserăm și să ștergem
ultimul element.
Și așa că trebuie să schimbăm
lucrurile acolo în ordine...
sau afară de acolo
pentru ca asta să funcționeze.
Și apoi, restul este
doar verificarea locală
dacă puteți repara proprietatea.
Misto.
Deci cam asta e, nu
chiar ceea ce ne-am dorit.
Deci acum avem log n amortize
insert și delete_max
în grămada noastră.
Nu am
acoperit încă construcția liniară.
În acest moment, este n log n
dacă inserați de n ori.
Și încă nu am acoperit cum să
facem din acesta un algoritm de sortare în loc
.
Așa că permiteți-mi să schițez fiecare dintre acestea.
Cred că primul este pe loc.
Deci, cum facem acest
algoritm pe loc?
Cred că vreau asta,
dar nu am nevoie de asta.
Așa că vrem să urmărim
sortarea prioritară a cozii.
Poate că vreau asta.
Dar nu vreau să fiu nevoit să-mi
cresc și să-mi micșorez gama.
Aș dori doar să încep
cu matricea în sine.
Deci asta este pe loc.
Deci, ceea ce vom
face este să spunem, OK, iată
matricea mea pe care vreau să o sortez.  Asta
mi-a fost dat.
Aceasta este intrarea pentru
sortarea cozii cu prioritate.
Și ce mi-aș dori este să construiesc
o coadă prioritară din ea.
Inițial, este gol.
Și apoi vreau să inserez
elementele pe rând, să spunem.
Deci, în general, ceea ce
voi face
este să mențin că Q
este un prefix al lui A.
Aceasta va fi
coada mea de prioritate.  Va
locui în această
submatrice... acest prefix.
Deci, cum inserez un articol nou?
Ei bine, eu doar cresc.
Deci, pentru a face o inserare, primul
pas este mărirea mărimii lui Q.
Apoi voi fi luat
următorul articol din A
și injectat în acest Q.
Și, în mod convenabil, dacă ne uităm la
codul nostru de inserare, care este aici,
primul lucru pe care îl vom fi  am vrut
să fac a fost adăugarea unui element
la sfârșitul matricei.
Așa că am făcut-o fără
nicio muncă reală, doar
muncă conceptuală.
Tocmai am spus, oh,
Q-ul nostru este unul mai mare.
Bum!
Acum, acesta este la
sfârșitul matricei.
nu mai am amortizat, de
fapt, pentru că nu ne
redimensionăm niciodată matricea,
spunem doar, oh,
acum Q este
un prefix puțin mai mare.  Pur și simplu
absoarbe
următorul element din A. În
mod similar, delete_max va reduce
,
la sfârșit,
dimensiunea lui Q. De ce este în regulă?
Pentru că la sfârșitul
operațiunii noastre delete_max--
nu chiar la sfârșit,
dar aproape la sfârșit--
am șters ultimul
element din matricea noastră.
Așa că tocmai am înlocuit
ultima ștergere cu o scădere,
iar aceasta va
micșora Q-ul cu 1.
Are exact același impact
ca liderul ultimului element.
Dar acum, este timpul constant,
cel mai rău caz nu este amortizat.
Și rezultatul este că nu
construim niciodată o matrice dinamică.
Folosim doar o porțiune
de A pentru a face asta.
Deci, ceea ce se va
întâmpla este că vom
absorbi toate articolele
în coada de prioritate
și apoi vom începe să le dam afară.  Pe
măsură ce îi dăm afară,
scoatem mai întâi cel mai mare element cheie
și îl punem aici, apoi pe
următorul cel mai mare, apoi pe
următorul cel mai mare și așa mai departe.
Elementul minim va
fi aici.
Și, bum, e rezolvat.
Acesta este motivul pentru care am făcut
max-heaps în loc de min-heaps,
este că, în cele din urmă, aceasta
va fi o matrice sortată în sus
cu max-ul la sfârșit.
Pentru că întotdeauna
scoatem obiecte la sfârșit.  Mai
întâi ștergem maximul.
Deci asta este ceea ce se
numește în mod normal heapsort.
Puteți aplica același truc
la sortarea prin inserare și sortarea prin selecție
și, de fapt, obțineți algoritmii de sortare prin
inserție și sortare selecție pe
care i-am
văzut care funcționează
în prefixele matricei.
Cool, așa că acum avem-- am
atins
y acolo sus, care
este algoritmul de sortare n log n
care este pe loc.
Deci ăsta a fost obiectivul nostru principal -
gruparea în grămada.
Permiteți-mi să menționez foarte repede că
puteți construi o grămadă în timp liniar
cu un truc inteligent.
Deci, dacă inserați
elementele pe rând,
aceasta ar corespunde
inserării în jos a matricei.
Și de fiecare dată când introduc un articol,
trebuie să merg în brad.
Deci aceasta ar fi suma
adâncimii fiecărui nod.
Dacă faci asta, obții n log n.
Aceasta este suma peste i a logului i.
Acesta se dovedește a fi n log n.
Este un log de factorial n.
Trucul tare este
, în schimb, să-ți imaginezi că
adaugi toate elementele
deodată și nu ai
îngrămădit nimic,
apoi să crești grămadă-- îmi pare rău, să adaugi
grămadă de jos în sus.
Așa că aici ne îngrămădim.
Acum, ne vom
îngrămădi.
Și surprinzător, așa e mai bine.
Pentru că aceasta este suma
înălțimilor nodurilor.
Și asta se dovedește a fi liniar.
Nu este evident.
Dar intuitiv, pentru o adâncime,
acesta este 0, acesta este log n
și avem o
tonă întreagă de frunze.
Deci chiar la nivelul frunzei,
puteți vedea, plătim n log n,
nu?
Pentru că sunt n dintre ele,
iar fiecare costă log n.
Aici jos, la
nivelul frunzelor, plătim constant.
Deoarece înălțimea
frunzelor este 1.
Aici, înălțimea
rădăcinii este log n.
Și asta e mai bine.
Acum plătim o
sumă mică pentru lucrul
din care sunt multe.
Nu este chiar o
serie geometrică,
dar se dovedește că aceasta este liniară.
Așa puteți
face o clădire liniară.
Pentru a reveni la întrebarea dvs.
despre arborii AVL de secvență, se
dovedește că puteți obține
toate aceleași limite
ca și grămezi, cu excepția
părții in loc,
luând un
arbore AVL de secvență, stocând
elementele într-o
ordine arbitrară și mărind
prin  max, care este o idee nebună.
Dar vă oferă și
un timp de construcție liniar.
Și da, mai sunt și alte
chestii distractive în notițele tale.
Dar mă voi opri aici.