שאלה על מיון ערימה איך אפשר להוכיח BUILD-HEAP מבצעת לכל היותר 2N-2 פעולות השוואה בין איברים?
L lionsh New member 19/4/06 #1 שאלה על מיון ערימה איך אפשר להוכיח BUILD-HEAP מבצעת לכל היותר 2N-2 פעולות השוואה בין איברים?
L lionsh New member 19/4/06 #2 לא משנה, פתרתי. BUILD-HEAP קוראת לHEPIFY N-1 פעמים. בכל קריאה לHEAPIFY מתבצעות שתי השוואות בין איברים. את הצומת הנוכחי עם הבן השמאלי והבן הימני. סה"כ 2N-2 השוואות.
לא משנה, פתרתי. BUILD-HEAP קוראת לHEPIFY N-1 פעמים. בכל קריאה לHEAPIFY מתבצעות שתי השוואות בין איברים. את הצומת הנוכחי עם הבן השמאלי והבן הימני. סה"כ 2N-2 השוואות.
R ron369 New member 20/4/06 #4 אני יכול אולי להסביר בקשר לתוחלת... (כלומר, למה תוחלת כל קריאה היא O(1), והחסם העליון על כולן הוא O). יעזור? (זה לא כתוב ומוכח בקורמן? יש קישור לספר בקישורים, אם אני לא טועה)
אני יכול אולי להסביר בקשר לתוחלת... (כלומר, למה תוחלת כל קריאה היא O(1), והחסם העליון על כולן הוא O). יעזור? (זה לא כתוב ומוכח בקורמן? יש קישור לספר בקישורים, אם אני לא טועה)
). יעזור? (זה לא כתוב ומוכח בקורמן? יש קישור לספר בקישורים, אם אני לא טועה)