Data Structures – Recitation 7
Shay Golan
1
ערימות בינאריות
2
פעולות נדרשות�תור עדיפויות - Priority Queue
3
תכונת הערימה
4
תכונת הערימה
5
80
25
20
30
22
5
12
11
ערימה בינארית
6
ערימה בינארית
7
80
45
20
8
15
12
5
70
21
33
7
90
מימוש ערימה בינארית
8
מימוש ערימה בינארית
9
80
45
20
8
15
12
5
70
21
33
7
90
90
80
70
20
45
33
21
5
12
8
15
7
1
2
3
4
5
6
7
8
9
10
11
12
Heapify
10
Heapify
11
80
45
20
8
15
12
5
70
21
33
7
30
Heapify
12
30
45
20
8
15
12
5
70
21
33
7
80
Heapify
13
45
30
20
8
15
12
5
70
21
33
7
80
Heapify
14
45
30
20
8
15
12
5
70
21
33
7
80
הגדלת ערך (ובדומה גם הכנסה)
15
הגדלת ערך
16
45
30
20
8
15
12
5
70
21
33
7
80
הגדלת ערך
17
45
30
20
8
15
50
5
70
21
33
7
80
הגדלת ערך
18
45
30
50
8
15
20
5
70
21
33
7
80
הגדלת ערך
19
50
30
45
8
15
20
5
70
21
33
7
80
הגדלת ערך
20
50
30
45
8
15
20
5
70
21
33
7
80
פעולות על ערימה בינארית
21
ערימת min-max
22
שאלה - ערימת MinMax
23
תשובה
24
תשובה
25
50
30
45
8
15
20
5
70
21
33
7
80
7
8
21
20
15
30
45
33
80
50
70
5
ערמת מקסימום
ערמת מינימום
ערימת חציון
26
שאלה – ערימת חציון
27
תשובה – ערימת חציון
28
תשובה ערימת חציון
29
מימוש הפעולות – ערימת חציון
30
מימוש הפעולות – ערימת חציון
31
תשובה
32
12
2
7
10
15
22
27
35
45
20
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
25
5
5
מספר האיברים בכל ערימה
תשובה
33
12
2
7
10
15
22
27
35
45
20
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
25
5
6
מספר האיברים בכל ערימה
תשובה
34
12
2
7
10
15
22
27
35
25
20
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
45
5
6
מספר האיברים בכל ערימה
תשובה
35
12
2
7
10
15
22
27
35
25
20
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
45
5
6
21
מספר האיברים בכל ערימה
תשובה
36
12
2
7
10
15
22
27
35
25
20
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
45
5
6
21
מספר האיברים בכל ערימה
תשובה
37
12
2
7
10
15
22
27
35
25
45
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
20
5
5
21
מספר האיברים בכל ערימה
תשובה
38
12
2
7
10
15
45
27
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
20
5
21
5
מספר האיברים בכל ערימה
תשובה
39
12
2
7
10
15
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
20
5
21
5
מספר האיברים בכל ערימה
תשובה
40
12
2
7
10
15
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
20
6
21
5
מספר האיברים בכל ערימה
תשובה
41
12
2
7
20
15
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
21
5
מספר האיברים בכל ערימה
תשובה
42
12
2
7
15
20
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
21
5
מספר האיברים בכל ערימה
תשובה
43
12
2
7
15
20
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
6
21
מספר האיברים בכל ערימה
תשובה
44
12
2
7
15
20
27
45
35
21
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
6
25
מספר האיברים בכל ערימה
תשובה
45
12
2
7
15
20
27
45
35
22
21
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
6
25
מספר האיברים בכל ערימה
מימוש הפעולות – ערימת חציון
46
הוצאת חציון
47
12
2
7
15
20
27
45
35
22
21
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
6
25
מספר האיברים בכל ערימה
הוצאת חציון
48
12
2
7
15
20
27
45
35
22
25
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
5
מספר האיברים בכל ערימה
הוצאת חציון
49
12
2
7
15
20
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
10
6
5
מספר האיברים בכל ערימה
הוצאת חציון
50
12
2
7
15
10
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
20
6
5
מספר האיברים בכל ערימה
הוצאת חציון
51
12
2
7
10
15
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
20
6
5
מספר האיברים בכל ערימה
הוצאת חציון
52
12
2
7
10
15
27
45
35
25
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
20
6
5
מספר האיברים בכל ערימה
הוצאת חציון
53
12
2
7
10
15
27
45
35
20
22
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
25
6
5
מספר האיברים בכל ערימה
הוצאת חציון
54
12
2
7
10
15
27
45
35
22
20
ערמת מקסימום
ערמת מינימום
(מצויירת הפוך)
25
6
5
מספר האיברים בכל ערימה
איבר k-בגודלו ממערכים ממוינים
55
56
57
12
20
22
28
45
49
55
101
107
200
65
90
5
7
13
16
8
14
15
87
19
24
29
33
85
88
91
99
58
12
20
22
28
45
49
55
65
90
5
7
13
16
8
14
15
87
19
24
29
33
85
88
91
99
101
107
200
מיזוג ערימות בינאריות
59
שאלה - מיזוג
60
תשובה
61
ערימות בינומיות
(מבוסס בחלקו על שקפים של רני הוד)
62
מוטיבציה
63
| ערימה בינארית | מטרה |
הכנסה | | |
החזרת מינימום | | |
הוצאת מינימום | | |
הקטנת מפתח | | |
בניית ערימה | | |
מיזוג | | |
עץ בינומי
64
עצים בינומיים
65
עצים בינומיים
66
עצים בינומיים
67
עצים בינומיים
68
עצים בינומיים
69
תכונות של עצים בינומיים
70
תכונה 1
71
תכונה 2
72
תכונה 3
73
תכונה 4
74
ערימה בינומית
75
ערימה בינומית
76
דוגמה
77
21
46
35
75
65
50
47
49
36
80
12
ייצוג
78
21
46
35
75
65
50
47
49
36
80
12
פעולת Link
79
75
65
50
12
38
35
42
15
פעולת Link
80
75
65
50
12
38
35
42
15
פעולת Link
81
75
65
50
12
38
35
42
15
פעולות של ערימה בינומית
82
פעולות - מיזוג
83
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
B2
B3
☐
☐
☐
B3
B4
מיזוג - דוגמה
84
21
46
35
75
65
50
47
49
36
80
12
23
95
83
53
48
96
41
77
40
32
25
17
10
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
Q1:
Q2:
מיזוג - דוגמה
85
21
46
35
75
65
50
47
49
36
80
12
23
95
83
53
48
96
41
77
40
32
25
17
10
Q1:
Q2:
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
☐
מיזוג - דוגמה
86
21
46
35
75
65
50
47
49
36
80
12
23
95
83
53
48
96
41
77
40
32
25
17
10
Q1:
Q2:
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
B2
☐
☐
מיזוג - דוגמה
87
75
65
50
47
49
36
80
12
95
83
53
48
96
41
77
40
32
25
17
10
Q1:
Q2:
21
46
35
23
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
B2
B3
☐
☐
☐
מיזוג - דוגמה
88
21
46
35
75
65
50
47
49
36
80
12
23
95
83
53
48
96
41
77
40
32
25
17
10
Q1:
Q2:
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
B2
B3
☐
☐
☐
מיזוג - דוגמה
89
21
46
35
75
65
50
47
49
36
80
12
23
95
83
53
48
96
41
77
40
32
25
17
10
Q1:
Q2:
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
B2
B3
☐
☐
☐
B3
B4
מיזוג - דוגמה
90
21
46
35
75
65
50
47
49
36
80
12
23
95
83
53
48
96
41
77
40
32
25
17
10
Q1:
Q2:
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
B2
B3
☐
☐
☐
B3
B4
זמן מיזוג
91
תחזוקת מינימום
92
תחזוקת מינימום
93
46
35
75
65
50
47
49
36
80
12
32
25
17
10
Q1:
B0
B1
☐
B3
Q2:
B0
☐
B2
B3
B1
B2
B3
☐
☐
☐
B3
B4
23
21
95
83
53
48
96
41
77
40
הכנסת איבר
94
הכנסת איבר
95
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
95
83
53
48
96
41
77
40
13
הכנסת איבר
96
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
95
83
53
48
96
41
77
40
13
הוצאת מינימום
97
הוצאת מינימום
98
13
95
83
53
48
96
41
77
40
32
25
17
10
הוצאת מינימום
99
13
95
83
53
48
96
41
77
40
32
25
17
הוצאת מינימום
100
13
95
83
53
48
96
41
77
40
32
25
17
הוצאת מינימום
101
13
95
83
53
48
96
41
77
40
32
25
17
הוצאת מינימום
102
13
95
83
53
48
96
41
77
40
32
25
17
הוצאת מינימום
103
13
95
83
53
48
96
41
77
40
32
25
17
הקטנת מפתח
104
הקטנת מפתח
105
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
95
83
53
48
96
41
77
40
13
הקטן ל2
הקטנת מפתח
106
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
2
83
53
48
96
41
77
40
13
הקטן ל2
הקטנת מפתח
107
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
83
2
53
48
96
41
77
40
13
הקטנת מפתח
108
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
83
48
53
2
96
41
77
40
13
הקטנת מפתח
109
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
83
48
53
40
96
41
77
2
13
הקטנת מפתח
110
46
35
75
65
50
47
49
36
80
12
32
25
17
10
23
21
83
48
53
40
96
41
77
2
13
הגדלת מפתח
111
בנייה
112
בנייה
113
Q:
B0
B1
B2
☐
☐
☐
סיכום
114
| ערימה בינארית | מטרה |
הכנסה | | |
החזרת מינימום | | |
הוצאת מינימום | | |
הקטנת מפתח | | |
בניית ערימה | | |
מיזוג | | |