ערימה בינומית – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־04:23, 18 במאי 2014

במדעי המחשב, ערמה בינומית היא סוג של מבנה הנתונים ערימה. היא מיוצגת בעזרת אוסף עצים בינומים. יתרונה הוא שהיא מאפשרת מיזוג שתי ערימות במהירות.

ערימה בינומית מאפשרת מימוש יעיל של מבנה הנתונים המופשט תור עדיפויות.

מבנה

ערימה בינומית ממומשת כאוסף של עצים בינומים. עץ בינומי מוגדר רקורסיבית: עץ מדרגה 0 הוא שורש בלבד, ועץ מדרגה i הוא חיבור של שני עצים מדרגה i-1, כאשר השורש של אחד מהם הוא הבן של השורש השני. בנוסף, כל אחד מהעצים מקיים את "כלל הערימה": הערך של כל צומת קטן יותר מכל בניו (ערימה כזאת נקראת "ערימת מנימום". ניתן גם לבנות "ערימת מקסימום", בה כל צומת גדול משני בניו).

בעץ בינומי מדרגה i יש $2^{i}$ קודקודים, והערמה בנויה כך שמכל דרגה יש עץ אחד לכל היותר. כתוצאה מכך יש דרך אחת ויחידה למבנה הערימה, שנובעת מהייצוג הבינארי של גודל הערימה. (לדוגמה, בערימה מגודל 25, שהוא 11001 בבסיס בינארי, יהיה עץ אחד מדרגה 0, עץ אחד מדרגה 3 ועץ אחד מדרגה 4). את שורשי העצים מחזיקים בדרך כלל ברשימה מקושרת כפולה (כלומר עם מצביעים אחורה).

פעולות

ערימה בינומית תומכת בפעולות הבאות:

הכנסה: כדי להכניס קודקוד חדש, מוסיפים אות תחילה כעץ חדש מדרגה 0. אם יש כבר כזה, מחברים אותם (כך שהקטן יהיה אבא של הגדול) ליצירת עץ אד מדרגה 1. אם גם כזה כבר יש, מחברים גם אותם וכן הלאה, עד שמגיעים לערימה תקינה. סיבוכיות הפעולה היא $O(\log n)$ (כש-n הוא גודל הערימה), אך ניתוח לשיעורין מביא לתוצאה של $O(1)$ (ומכאן שבניית ערימה מ-n איברים לוקחת $O(n)$ ).
מחיקת המינימום: מחזיקים מצביע לאיבר המינימלי, כך שמציאתו לוקחת $O(1)$ . מוחקים אותו. כיוון שילדיו של עץ מדרגה i הם שורשים של עצים מדרגות

i-1‏,...,0,1, מבצעים מיזוג (המתואר בפיסקה הבאה) בין העצים הללו לשאר הערימה. סיבוכיות: $O(\log n)$ .

מיזוג: בהינתן שתי ערימות, ממזגים אותן בדומה לחיבור בינארי: עוברים על הדרגות מהקטנה לגדולה, ובכל דרגה, אם יש רק עץ אחת מדרגה כזו מכניסים לערימה המאוחדת, ואם יש שניים, מאחדים אותם ומתייחסים אליהם כאל עץ מדרגה גדולה יותר (בדומה לנשא בחיבור רגיל) כיוון שישנם כ-log n עצים בכל ערימה, הסיבוכיות היא $O(\log n)$ .
מחיקה: כיוון שערימה אינה תומכת בחיפוש, מחיקה צריכה לבוא עם מצביע לאיבר הנמחק. כדי למחוק מחליפם את הצומת עם אביו, ואז שוב עד שהוא מגיע לשורש (פעולה זאת לוקחת כעומק המקסימלי של עץ שהוא כ-log n), ואז מוחקים אותו וממזגים את בניו עם שאר הערימה. סיבוכיות: $O(\log n)$ .
הקטנת מפתח: בהינתן מצביע לצומת מסוים, מקטינים את המפתח, ואם הוא קטן מאביו, מחליפים ביניהם, ושוב אם הוא קטן מאבין מחליפים בינהים עד שהוא גדול מאביו (או מגיע לשורש). $O(\log n)$ .

וריאציות

ערימה בינומית עצלה

ערימה בינומית עצלה ממומשת בדומה לערמה, אך היא לא משמרת את המבנה כל הזמן: בפעולות הכנסה ומיזוג פשוט משרשרים את האיבר החדש או הערימה החדשה לקיימת (ב- $O(1)$ ) ואילו בפעולת המחיקה מתקנים תוך כדי את הערימה לערימה בינומית תקינהץ פעולה זאת לוקחת $O(n)$ , אך בניתוח לשיעורין עלותה הוא $O(\log n)$ .

ערימת פיבונאצ'י

בערימת פיבונאצ'י העצים כלל אינם עצים בינומיים: בכל פעולת הקטנת הערך חותכים את הצומת ויוצרים ממנו עץ חדש, וכאשר מוחקים כך שני בנים של צומת חותכים גם אותו. כתוצאה מכך העלות של פעולת הקטנת המפתח עולה ל- $O(n)$ , אך עלותה לשיעורין יורדת ל- $O(1)$ . בשל כך היא טובה לאלגוריתמים שדורשים הקטנות רבות של המפתחות (כדוגמת אלגוריתם דייקסטרה שבערימת פיבונאצ'י סיבוכיותו היא $\ O(|E|+|V|\log |V|)$ לעומת $\ O(|E|\log |V|)$ בערימה בינארית).

@@ שורה 7: / שורה 7: @@
 ערימה בינומית ממומשת כאוסף של [[עץ בינומי|עצים בינומים]]. עץ בינומי מוגדר [[רקורסיה|רקורסיבית]]: עץ מדרגה 0 הוא שורש בלבד, ועץ מדרגה i הוא חיבור של שני עצים מדרגה i-1, כאשר השורש של אחד מהם הוא הבן של השורש השני. בנוסף, כל אחד מהעצים מקיים את "כלל הערימה": הערך של כל צומת קטן יותר מכל בניו (ערימה כזאת נקראת "ערימת מנימום". ניתן גם לבנות "ערימת מקסימום", בה כל צומת גדול משני בניו).
-בעץ בינומי מדרגה i יש <math>2^i</math> קודקודים, והערמה בנויה כך שמכל דרגה יש עץ אחד לכל היותר. כתוצאה מכך יש דרך אחת ויחידה למבנה הערימה, שנובעת מהייצוג ה[[בינארי]] של גודל הערימה. (לדוגמה, בערימה מגודל 25, שהוא 11001 בבסיס בינארי, יהיה עץ אחד מדרגה 0, עץ אחד מדרגה 3 ועץ אחד מדרגה 4).
+בעץ בינומי מדרגה i יש <math>2^i</math> קודקודים, והערמה בנויה כך שמכל דרגה יש עץ אחד לכל היותר. כתוצאה מכך יש דרך אחת ויחידה למבנה הערימה, שנובעת מהייצוג ה[[בסיס בינארי|בינארי]] של גודל הערימה. (לדוגמה, בערימה מגודל 25, שהוא 11001 בבסיס בינארי, יהיה עץ אחד מדרגה 0, עץ אחד מדרגה 3 ועץ אחד מדרגה 4). את שורשי העצים מחזיקים בדרך כלל ב[[רשימה מקושרת]] כפולה (כלומר עם מצביעים אחורה).
 ==פעולות==
@@ שורה 13: / שורה 13: @@
 ערימה בינומית תומכת בפעולות הבאות:
-* '''הכנסה''': כדי להכניס קודקוד חדש, מוסיפים אות תחילה כעץ חדש מדרגה 0. אם יש כבר כזה, מחברים אותם (כך שהקטן יהיה אבא של הגדול) ליצירת עץ אד מדרגה 1. אם גם כזה כבר יש, מחברים גם אותם וכן הלאה, עד שמגיעים לערימה תקינה. [[סיבוכיות]] הפעולה היא <math>O(log n)</math> (כש-n הוא גודל הערימה), אך [[ניתוח לשיעורין]] מביא לתוצאה של <math>O(1)</math> (ומכאן שבניית ערימה מ-n איברים לוקחת <math>O(n)</math>).
+* '''הכנסה''': כדי להכניס קודקוד חדש, מוסיפים אות תחילה כעץ חדש מדרגה 0. אם יש כבר כזה, מחברים אותם (כך שהקטן יהיה אבא של הגדול) ליצירת עץ אד מדרגה 1. אם גם כזה כבר יש, מחברים גם אותם וכן הלאה, עד שמגיעים לערימה תקינה. [[סיבוכיות]] הפעולה היא <math>O(\log n)</math> (כש-n הוא גודל הערימה), אך [[ניתוח לשיעורין]] מביא לתוצאה של <math>O(1)</math> (ומכאן שבניית ערימה מ-n איברים לוקחת <math>O(n)</math>).
 * '''מחיקת המינימום''': מחזיקים [[מצביע]] לאיבר המינימלי, כך שמציאתו לוקחת <math>O(1)</math>. מוחקים אותו. כיוון שילדיו של עץ מדרגה i הם שורשים של עצים מדרגות
-,1,...,i-1 מבצעים מיזוג (המתואר בפיסקה הבאה) בין העצים הללו לשאר הערימה. סיבוכיות: <math>O(log n)</math>.
+i-1{{כ}},...,0,1, מבצעים מיזוג (המתואר בפיסקה הבאה) בין העצים הללו לשאר הערימה. סיבוכיות: <math>O(\log n)</math>.
-* '''מיזוג''': בהינתן שתי ערימות, ממזגים אותן בדומה ל[[חיבור]] בינארי: עוברים על הדרגות מהקטנה לגדולה, ובכל דרגה, אם יש רק עץ אחת מדרגה כזו מכניסים לערימה המאוחדת, ואם יש שניים, מאחדים אותם ומתייחסים אליהם כאל עץ מדרגה גדולה יותר (בדומה לנשא בחיבור רגיל) כיוון שישנם כ-log n עצים בכל ערימה, הסיבוכיות היא <math>O(log n)</math>.
+* '''מיזוג''': בהינתן שתי ערימות, ממזגים אותן בדומה ל[[חיבור]] בינארי: עוברים על הדרגות מהקטנה לגדולה, ובכל דרגה, אם יש רק עץ אחת מדרגה כזו מכניסים לערימה המאוחדת, ואם יש שניים, מאחדים אותם ומתייחסים אליהם כאל עץ מדרגה גדולה יותר (בדומה לנשא בחיבור רגיל) כיוון שישנם כ-log n עצים בכל ערימה, הסיבוכיות היא <math>O(\log n)</math>.
-* '''מחיקה''': כיוון שערימה אינה תומכת בחיפוש, מחיקה צריכה לבוא עם מצביע לאיבר הנמחק. כדי למחוק מחליפם את הצומת עם אביו, ואז שוב עד שהוא מגיע לשורש (פעולה זאת לוקחת כעומק המקסימלי של עץ שהוא כ-log n), ואז מוחקים אותו וממזגים את בניו עם שאר הערימה. סיבוכיות: <math>O(log n)</math>.
+* '''מחיקה''': כיוון שערימה אינה תומכת בחיפוש, מחיקה צריכה לבוא עם מצביע לאיבר הנמחק. כדי למחוק מחליפם את הצומת עם אביו, ואז שוב עד שהוא מגיע לשורש (פעולה זאת לוקחת כעומק המקסימלי של עץ שהוא כ-log n), ואז מוחקים אותו וממזגים את בניו עם שאר הערימה. סיבוכיות: <math>O(\log n)</math>.
-* '''הקטנת מפתח''': בהינתן מצביע לצומת מסוים, מקטינים את המפתח, ואם הוא קטן מאביו, מחליפים ביניהם, ושוב אם הוא קטן מאבין מחליפים בינהים עד שהוא גדול מאביו (או מגיע לשורש). <math>O (log n)</math>.
+* '''הקטנת מפתח''': בהינתן מצביע לצומת מסוים, מקטינים את המפתח, ואם הוא קטן מאביו, מחליפים ביניהם, ושוב אם הוא קטן מאבין מחליפים בינהים עד שהוא גדול מאביו (או מגיע לשורש). <math>O (\log n)</math>.
 ==וריאציות==
 ===ערימה בינומית עצלה===
-ערימה בינומית עצלה ממומשת בדומה לערמה, אך היא לא משמרת את המבנה כל הזמן: בפעולות הכנסה ומיזוג פשוט משרשרים את האיבר החדש או הערימה החדשה לקיימת (ב-<math>O(1)</math>) ורק בפעולת מחיקה יוצרים ערימה. פעולה זאת לוקחת <math>O(n)</math>, אך בניתוח לשיעורין עלותה הוא <math>O(log n)</math>.
+ערימה בינומית עצלה ממומשת בדומה לערמה, אך היא לא משמרת את המבנה כל הזמן: בפעולות הכנסה ומיזוג פשוט משרשרים את האיבר החדש או הערימה החדשה לקיימת (ב-<math>O(1)</math>) ואילו בפעולת המחיקה מתקנים תוך כדי את הערימה לערימה בינומית תקינהץ פעולה זאת לוקחת <math>O(n)</math>, אך בניתוח לשיעורין עלותה הוא <math>O(\log n)</math>.
 ===ערימת פיבונאצ'י===
-בערימת פיבונאצ'י העצים כלל אינם עצים בינומיים: בכל פעולת הקטנת הערך חותכים את הצומת ויוצרים ממנו עץ חדש, וכאשר מוחקים כך שני בנים של צומת חותכים גם אותו. כתוצאה מכך העלות של פעולת הקטנת המפתח עולה ל-<math>O(n)</math>, אך עלותה לשיעורין יורדת ל-<math>O(1)</math>. בשל כך היא טובה לאלגוריתמים שדורשים הקטנות רבות של המפתחות (כדוגמת [[אלגוריתם דייקסטרה]] שבערימת פיבונאצ'י סיבוכיותו היא <math>\ O(|E|+|V|log|V|)</math> לעומת  <math>\ O(|E|log|V|)</math>  בערימה בינארית).
+בערימת פיבונאצ'י העצים כלל אינם עצים בינומיים: בכל פעולת הקטנת הערך חותכים את הצומת ויוצרים ממנו עץ חדש, וכאשר מוחקים כך שני בנים של צומת חותכים גם אותו. כתוצאה מכך העלות של פעולת הקטנת המפתח עולה ל-<math>O(n)</math>, אך עלותה לשיעורין יורדת ל-<math>O(1)</math>. בשל כך היא טובה לאלגוריתמים שדורשים הקטנות רבות של המפתחות (כדוגמת [[אלגוריתם דייקסטרה]] שבערימת פיבונאצ'י סיבוכיותו היא <math>\ O(|E|+|V|\log|V|)</math> לעומת  <math>\ O(|E|\log|V|)</math>  בערימה בינארית).
 [[קטגוריה:מבני נתונים]]