הכנסה למערך של ערימות

מנהל: TA_Isana

שלח תגובה
Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

הכנסה למערך של ערימות

שליחה על ידי Brk » 21:03 27/05/2010

האם בבניית ערימה,בעצם מכניסים את האיברים בתת המערך איך שהם לערימה ואז עושים עוברים על האיברים הנדרשים מn/2 עד 1 ועושים maxHeapify תקנו אותי אם אני טועה? בעצם סה"כ אני יבצע הכנסה של n איברים למערך של מערכים,ועל כול מערך כזה אני יבצע בניית ערימה שתעלה לי n/k*(log(n/k)) האם זה לא חריגה מזמני ריצה?

ושאלה נוספת:
בהרצאות מופיע בפרק של הערימות הכנסה לתור עדיפויות,האם זה לא הכנסה לערימה או שזה לא קשור לערימות

Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: הכנסה למערך של ערימות

שליחה על ידי Brk » 22:27 27/05/2010

Bump,אפשר תשובה

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: הכנסה למערך של ערימות

שליחה על ידי TA_Ariel » 22:35 27/05/2010

בניית ערימה לוקחת O(n) לא O(nlogn).

Brk
הודעות: 87
הצטרף: 17:58 25/10/2009

Re: הכנסה למערך של ערימות

שליחה על ידי Brk » 23:08 27/05/2010

TA_Ariel כתב:בניית ערימה לוקחת O(n) לא O(nlogn).
http://www.cs.bgu.ac.il/~ds102/wiki.fil ... tion09.pdf
לפי המצגת רשום שיש O(n) קריאות לmaxheapify סה"כ O(nlogn)

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: הכנסה למערך של ערימות

שליחה על ידי TA_Ariel » 23:21 27/05/2010

תמשיך עוד שני שקפים למטה.

שלח תגובה

חזור אל “- מבני נתונים 2010”