(Binary) Heap. Binary tree yang menyimpan pasangan prioritas (atau prioritas elemen) pada node Property Heap :

heap wijanarto

(Binary) Heap • Binary tree yang menyimpan pasangan prioritas (atau prioritas elemen) pada node • Property Heap : – Struktural – Semua level kecuali yang terakhir berisi penuh, level terakhir boleh tidak penuh (berisi 1 anak) tetapi harus terisi.

– Heap – Prioritas (elemen) node setidaknya sama atau sebesar parentnya (nilai elemen dalam heap)

(Binary) Heap 1 1 1 7

1 3

1 8

4 3

2 1

2 3

2 6

1 9

2 9

3 1

1 7

Bukan Heap • Heap Violated

1 1

1 9

1 3

1 8

4 3

2 1

2 3

2 6

1 9

2 9

3 1

1 7

Bukan Heap • Level terakhir

1 1

• Ada yang kosong

1 7

1 3

1 8

4 3

2 1

2 6

1 9

2 9

Level terakhir seharusnya ada 4 node saja

3 1

1 7

Menemukan elemen Terkecil • Elemen dengan prioritas terkecil selalu berada pada posisi root dalam heap • Hal ini karena jika tidak maka prioritas tersebut akan menjadi parent dengan prioritas lebih kecil dan hal ini melanggar heap property • Dengan demikian findmin() dapat di lakukan selama waktu O(1)

Menemukan elemen Terkecil Findmin(a[]) return a[1];

Height dari Heap • Diberikan heap dengan n Node dan ketinggian (height) h • Recall: Complete Binary Tree dengan Height h memiliki 2h+1-1 node • Dengan demikian 2h-1<=2h+1-1 • n= log2 h

Implementasi Heap • Parent (i){return i/2 } • Left(i){return 2i}

1 1

1 7

1 3

• Right(i){rreturn 2i+1} 1 8

Parent(5) 2 (17) Left(3) 6 (19)

2 1

4 3

Right(3) 7 17)

2 3

1 A Level 0

1 1

2

1 7

3

1

Heap property : A[parent(i)]<=A[i]

1 3

1 9

2 6

4

1 8

5

6

2 1

1 9

2

7

1 7

8

4 3

9 10 2 3

2 6

3

1 7

Implementasi Heap • Secara implisit tree dalam link, dengan anak node i adalah 2i dan 2i+1 • Kenapa hal ini bermanfaat ? – Dalam representasi binary , perkalian atau pembagian dengan 2 merupakan pergeseran ke kanan atau ke kiri (a** == shl(a) atau a//==shr(a)) – Menambah 1 sama dengan menambah pada bit terendah

Penyisipan dalam Heap • Sisipkan 12

1 1

1 7

1 3

1 8

4 3

2 1

2 3

2 6

1 7

19

2 9

3 1

12

ara struktur maka kita akan tambahkan node Secara struktur sudah benar evel terakhir Tetapi secara heap tree ini bukan heap (krn 12 < dari parent) Shg kita harus menukarnya


1 1

1 7

13

1 8

4 3

2 1

2 3

2 6

1 7

12

2 9

3 1

19

ara struktur maka kita akan tambahkan node Secara struktur sudah benar evel terakhir Tetapi secara heap tree ini bukan heap (krn 12 < dari parent) Shg kita harus menukarnya


1 1

• Sisipkan 8

1 7

13

1 8

4 3

2 1

2 3

2 6

12

2 9

3 1

17

19

8


1 1

• Sisipkan 8

1 7

13

1 8

4 3

2 1

2 3

2 6

12

2 9

3 1

8

19

17


11

• Sisipkan 8

1 7

8

1 8

4 3

2 1

2 3

2 6

12

2 9

3 1

13

19

17


8

• Sisipkan 8

1 7

11

1 8

4 3

2 1

2 3

2 6

12

2 9

3 1

13

19

17

Cara menyisipkan lainnya • Perbesar heap

Memakai jalur dari root Utk menyisipkan node

1 7 2 1

2 3

12

1 3

1 8

4 3

1 1

2 6

19

2 9

3 1

1 7

Cara menyisipkan lainnya • Perbesar heap

1 1

Memakai jalur dari root Utk menyisipkan node

12

1 emukan elemen dengan 7 rioritas tertinggi yang ebih besar dari lemen yang 1 kan di sisipkan 8

4 3

2 3

13

2 1

2 6

19

2 9

Sisipkan elemen pada lokasi tersebut dan geser ke bawah elemen lainnya sesuai jalur yang di pilih

3 1

1 7

Cara menyisipkan lainnya 1 1 1 7

1 2

1 8

4 3

2 1

2 3

2 6

1 7

13

2 9

3 1

19

Kebenaran Insertion • Node yang isinya berubah berada pada path

1 1

1 7

12

1 3

1 8

4 3

2 1

2 3

2 6

19

2 9

3 1

1 7

Kebenaran Insertion • Node yang isinya berubah berada pada path • Heap property terlanggar hanya pada node anaknya 1 1

1 7

12

1 3

1 8

4 3

2 1

2 3

2 6

19

2 9

3 1

1 7


• Isi yang baru berprioritas lebih kecil 12

dari sebelumnya

1 7

1 3

1 8

4 3

2 1

2 3

2 6

19

2 9

3 1

1 7


• Isi yang baru berprioritas lebih kecil 12

dari sebelumnya

1 7

13

1 8

4 3

2 1

2 3

2 6

19

2 9

3 1

1 7


• Isi yang baru berprioritas lebih kecil dari sebelumnya

1 7

12

• Shg heap property aman 1 8

4 3

2 1

2 3

2 6

1 7

13

2 9

3 1

19

Heapify(i) • i adalah index array A • Binary tree yang berakar di Left(i) dan Right(i) adalah heap • Tetapi, A[i] harus lebih besar dari anaknya, sehingga terjadi violated pada heap property • Fungsi Heapify membuat binary tree berakar di i pd heap dengan memindahkan A[i] ke bawah heap

Heapify • Ini bukan heap Heap property violated pada node dg index 1 tetapi Subtree pada akar 2 dan 3 adlaah heap Heapify (1)

1 7

1 0

1 1

1 6

4 3

Ini heap

2 1

2 3

2 6

1 2

13

2 9

3 1

19

Cara kerja Heapify • Heapify akan melihat dua anak dari root yang violated • Memilih prioritas pada kedua anak tersebut yang

17

terkecil, lalu menukar dengan rootnya

1 1

10

1 6

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19


10


1 1

17

2 1

16

4 3

2 3

2 6

1 2

13

2 9

3 1

19


10


1 1

16

2 1

17

43

2 3

2 6

1 2

13

2 9

3 1

19

Cara kerja Heapify lainnya • Heapify(i) melacak path tree ke bawah 1 7

1 0

1 1

1 6

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

Cara kerja Heapify lainnya • Heapify(i) melacak path tree ke bawah 1 7

1 0

1 1

1 6

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

Cara kerja Heapify lainnya • Heapify(i) melacak path tree ke bawah • Node terakhir pada path (misal j) memiliki baik A[left(j)], A[right(j)] yang lebih besar dari A[i] 1 7

1 0

1 1

1 6

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

Cara kerja Heapify lainnya • Heapify(i) melacak path tree ke bawah • Node terakhir pada path (misal j) memiliki baik A[left(j)], A[right(j)] yang lebih besar dari A[i] 1 7

• Seluruh elemen path Memiliki prioritas lebih

1 0

1 1

kecil dari saudaranya 1 6

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

Cara kerja Heapify lainnya • Heapify(i) melacak path tree ke bawah • Node terakhir pada path (misal j) memiliki baik A[left(j)], A[right(j)] yang lebih besar dari A[i] • Seluruh elemen path 17

Memiliki prioritas lebih kecil dari saudaranya • Seluruh elemen pd path ini di pindahkan ke atas

4 3

1 1

10

16

2 1

2 3

2 6

1 2

13

2 9

3 1

19

Cara kerja Heapify lainnya • Heapify(i) melacak path tree ke bawah • Node terakhir pada path (misal j) memiliki baik A[left(j)], A[right(j)] yang lebih besar dari A[i] • Seluruh elemen path 10

Memiliki prioritas lebih kecil dari saudaranya 16

• Seluruh elemen pd path ini

17

di pindahkan ke atas

2 1

• A[i] pindah ke posisi j 4 3

1 1

2 3

2 6

1 2

13

2 9

3 1

19

Run Time Analisis • Heap dengan n node mempunyai height O(log n) • Selama penyisipan kita harus memindahkan elemen ke atas • Dengan demikian setidaknya di perlukan O(log n) langkah • Dalam Heapify, elemen hrs di pindahkan ke akhir level, dan dengan demikian heapify perlu O(log n) langkah juga

Operasi Binary Heap • Delete-Min • Building heap dalam O(n) time • Heapsort

Delete Minimum • Elemen minimum adalah elemen pada top heap • Kita dapat menghapus elemen tersebut dan memindahkan anaknya ke atas untuk mengisi ruang yang kosong karena penghapusan tadi • Ruang yang kosong pada tree di pindahkan ke bawah • Di akhiri pada setiap posisi pada akhir level • Hasilnya tree menjadi tidak ada yang kosong pada akhir levelnya

Delete-min

dalam heap 8

1 0

1 1

1 8

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap

1 0

1 1

1 8

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap

1 0

1 1

1 8

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap

1 1

10

1 8

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap 10 1 1

1 8

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap 10 1 1

2 1

18

4 3

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap 10 1 1

18

2 1

4 3

18

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap 10 1 1

18

2 1

23

4 3

2 6

1 2

13

2 9

3 1

19

17

Pelanggaran terhadap property struktur

Delete-min

dalam heap (2)

• Ganti elemen top dengan elemen terakhir dalam heap 8

1 0

1 1

1 6

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap (2)

• Ganti elemen top dengan elemen terakhir dalam heap 1 0

1 1

1 6

4 3

2 1

2 3

2 6

1 2

13

2 9

3 1

19

17

Delete-min

dalam heap (2)


• Lakukan Heapify(1) 10

16

43

11

11

23

2 6

1 2

13

2 9

3 1

19

Delete-min

dalam heap (2)



16

43

11

11

23

2 6

1 2

13

2 9

3 1

19

Delete-min

dalam heap (2)



17

43

11

21

23

2 6

1 2

13

2 9

3 1

19

Building Heap • Dimulai dari bawah ke atas • Semua leaves adalah heap Build-Heap (A) for in/2 downto 1 do Heapify(A,i)

ren leaves berupa heap di mulai dari parent leaves terakhir 1 6

2 3

4 3

2 6

1 0

2 1

1 2

8

3 1

13

2 9

1 1

19

17


ren leaves berupa heap di mulai dari parent leaves terakhir

akukan Heapify (pada node tsb)

1 6

2 3

4 3

2 6

1 0

2 1

1 2

8

3 1

13

2 9

1 1

19

17




1 6

2 3

4 3

2 6

1 0

2 1

1 2

8

31

13

2 9

1 1

19

17




1 6

2 3

4 3

2 6

1 0

2 1

1 2

8

1 7

13

2 9

11

19

31




1 6

2 3

4 3

2 6

1 0

11

21

1 2

8

2 9

13

1 7

19

31




1 6

2 3

4 3

2 6

1 0

11

8

1 2

21

2 9

13

1 7

19

31




1 6

2 3

4 3

26

1 0

11

8

1 2

21

2 9

13

1 7

19

31




1 6

2 3

4 3

11

1 0

8

1 2

21

1 7

26

2 9

13

19

31




1 6

2 3

4 3

11

1 0

8

1 2

21

1 7

13

2 9

26

19

31

Building Heap • Dimulai dari bawah ke atas • Semua leaves adalah heap Build-Heap (A) for in/2 downto 1 do Heapify(A,i) 43



2 3

1 6

1 0

11

8

1 2

21

1 7

13

2 9

26

19

31


11

8



2 3

1 6

1 0

43

1 2

21

1 7

13

2 9

26

19

31


11

8



23

1 6

1 0

21

1 2

43

1 7

13

2 9

26

19

31

Building Heap • Dimulai dari bawah ke atas • Semua leaves adalah heap Build-Heap (A) for in/2 downto 1 do Heapify(A,i) 23



8

1 6

1 0

11

21

1 2

43

1 7

13

2 9

26

19

31


11

1 0



8

1 6

23

21

12

43

1 7

13

2 9

26

19

31

Analisis Building heap • Kebenaran : induksi pada i, semua akar tree pada m>i adalah heap • Run time : n call pada Heapify = n O(log n)=O(n log n) • Height node : panjang dari jalur terpanjang dari node ke leaf • Height tree: height node • Time Heapify(i)=O(height of subtree berakar i) • Asumsi : jum node n=2k-1 (complete binary tree)

Analisis Building heap (2) • Untuk n/2 node dngan height 1, heapify membutuhkan setidaknya 1 kali tukar • Untuk n/4 node dngan height 2, heapify membutuhkan setidaknya 2 kali tukar • Untuk n/2i node dngan height i, heapify membutuhkan setidaknya i kali tukar • Jadi total jumlah pertukaran : n +1  n +1 n +1  T ( n) = O + .2 + .3 + ... + 1 − k  4 8  2  log n log n  i i i/2 = O (n + 1).∑ karena ∑ = = 2 = O ( n) 2 2 2 ( i − 1 / 2 ) n =i n =i  

Bagaimana terjadi O(n) ? ∞

1 x = if x < 1 // diferensiasi ∑ 1− x i =0 i

∞

∑i − x

i −1

i =0 ∞

∑i − x i =0

i −1

1 = // kalikan → x 2 (1 − x) x 1 = // masukan → x = 2 ( x − x) 2

∞

i 1/ 2 = =2 ∑ i 1/ 4 i =0 2

Jadi O(n)

Heapsort • Buat heap

8

Lakukan delete-min Secara berulang hingga

1 0

1 1

Heap mjd kosong 1

2 1

• Lakukan sort pada, array2

1 7

13

Pindahkan (tukar) 1 6

elemen yang di hapus di akhir heap

2 3

4 3

2 9

2 6

19

31

Proses heapsort • Delete-min

8

1 1

10

1 2

1 6

2 1

2 3

13

4 3

1 7

13

2 9

2 6

19

31

Proses heapsort • Heapify (1)

31

1 1

10

1 2

1 6

2 1

2 3

4 3

1 7

13

2 9

2 6

19

8


10

1 1

31

12

16

21

23

43

17

13

29

26

19

8


10

1 1

12

31

16

21

23

43

17

13

29

26

19

8


10

1 1

12

16

31

21

23

43

17

13

29

26

19

8


10

1 1

12

16

31

21

23

43

17

13

29

26

19

8

Dihapus dengan delete-min Menghasilkan elemen tersortir


19

1 1

12

16

31

21

23

43

17

13

29

26

10

8


Proses heapsort • Heapify(1)

19

11

12

16

31

21

23

43

17

13

29

26

10

8



11

19

12

16

31

21

23

43

17

13

29

26

10

8



11

13

12

16

31

21

23

43

17

19

29

26

10

8



26

13

12

16

31

21

23

43

17

19

29

11

10

8



26

13

12

16

31

21

23

43

17

19

29

11

10

8



12

13

26

16

31

21

23

43

17

19

29

11

10

8



12

13

16

26

31

21

23

43

17

19

29

11

10

8



12

13

16

23

31

21

26

43

17

19

29

11

10

8



29

13

16

23

31

21

26

43

17

19

12

11

10

8



29

13

16

23

31

21

26

43

17

19

12

11

10

8



13

29

16

23

31

21

26

43

17

19

12

11

10

8



13

17

16

23

31

21

26

43

29

19

12

11

10

8



13

17

16

23

31

21

26

43

29

19

12

11

10

8



43

17

16

23

31

21

26

13

29

19

12

11

10

8



16

17

43

23

31

21

26

13

29

19

12

11

10

8



16

17

21

23

31

43

26

13

29

19

12

11

10

8



26

17

21

23

31

43

16

13

29

19

12

11

10

8



17

26

21

23

31

43

16

13

29

19

12

11

10

8



17

19

21

23

31

43

16

13

29

26

12

11

10

8



31

19

21

23

17

43

16

13

29

26

12

11

10

8



19

31

21

23

17

43

16

13

29

26

12

11

10

8


Proses heapsort • Delete-Min

19

26

21

23

17

43

16

13

29

31

12

11

10

8



29

26

21

23

17

43

16

13

19

31

12

11

10

8



21

26

29

23

17

43

16

13

19

31

12

11

10

8



21

26

23

29

17

43

16

13

19

31

12

11

10

8



31

26

23

29

17

43

16

13

19

21

12

11

10

8



23

26

31

29

17

43

16

13

19

21

12

11

10

8



23

26

29

31

17

43

16

13

19

21

12

11

10

8



43

26

29

31

17

23

16

13

19

21

12

11

10

8



26

43

29

31

17

23

16

13

19

21

12

11

10

8



26

43

29

31

17

23

16

13

19

21

12

11

10

8



31

43

29

26

17

23

16

13

19

21

12

11

10

8



29

43

31

26

17

23

16

13

19

21

12

11

10

8


Proses heapsort • Hepaify(1)

43

29

31

26

17

23

16

13

19

21

12

11

10

8



31

29

43

26

17

23

16

13

19

21

12

11

10

8



43

29

31

26

17

23

16

13

19

21

12

11

10

8



43

29

31

26

17

23

16

13

19

21

12

11

10

8


Run time operasi heap • Insert():O(log n) • Heapify(): O(log n) • Findmin(): O(1) • Deletemin(): O(log n) • Buildheap(): O(n) • Heapsort(): O(n log n)

Psuedo code • PARENT(i) return i/2 • LEFT(i) return 2i • RIGHT(i) return 2i + 1

Tukar Tukar (a,b) temp=a a=b b=temp

Heapify HEAPIFY(A, i) l  LEFT(i) r  RIGHT(i) if l <=heap-size[A] and A[l] > A[i] then largest  l else largest  i If r <=heap-size[A] and A[r] > A[largest] then largest  r if largest!= i then exchange A[i]<--> A[largest] HEAPIFY(A,largest)

Shiftdown ShiftDown(A,i) ki repeat jk if 2j<=length(A) and A[2j]>A[k] then

k2j

if 2jA[k] then

k2j+1

Tukar (A[j],A[k]) until j==k

Shiftup Shiftup(A,i) ki repeat jk if j>i and A[j%2]
Buildheap dan Makeheap BUILDHEAP(A) heap-size[A] length[A] for i length A/2  downto 1 do HEAPIFY(A, i) Atau Makeheap(A) for (i  A/2 ) downto 1 ShiftDown(A,i)

FindMax-min, DelMax-min Findmax(A) return A[1]; FindMin(A) return A[n] DelMax(A) A[1]A[n] ShiftDown(A[1..n-1],1) DelMin(A) A[n]A[1] ShiftUp(A[1..n-1],n)

InsertNode InsertNode(A,v) A[n+1]v Shiftup(A[1..n-1],n+1)

Heapsort Heapsort (A) makeheap(A) for in downto 2 do tukar(A[1],A[i]) Shiftdow(A[1..i-1],1) Atau HEAPSORT(A) BUILDHEAP(A) for i length[A] downto 2 do tukar(A[1],A[i]) heap-size[A]heap-size[A]-1 HEAPIFY(A, 1)

(Binary) Heap. Binary tree yang menyimpan pasangan prioritas (atau prioritas elemen) pada node Property Heap :

Recommend Documents