هرم

هرم بیشینه (یا کمینه) یک داده‌ساختار درختی است با این ویژگی که هر مقدار متناظر هر رأ س بیشتر (کمتر) یا مساوی فرزندهای خود است. بدین ترتیب عنصر بیشینه (کمینه) در ریشه قرار می‌گیرد. هرم های مختلف عملیات‌های مختلفی را پشتیبانی می کنند. عملیات های پایه‌ای یک هرم بیشینه عبارتند از: یافتن عنصر بیشینه، حذف عنصر بیشینه و درج

هرم معمولاً با آرایه پیاده‌سازی می‌شود و نیاز به اشاره‌گر ندارد. اگر ریشه‌‌ی هرم را اندیس ۱ در نظر بگیریم، می توانیم فرزندهای اندیس $x$ را $2x$ و $2x+1$ فرض کنیم.

عنصر بیشینه در ریشه قرار دارد. برای درج، عنصر جدید را در آخر هرم افزوده و تا جایی که باید آن را بالا می آوریم. برای حذف عنصر بیشینه، آن را با آخرین عنصر هرم جابه‌جا می‌کنیم و سپس سعی می‌کنیم شرط هرم را برقرار کنیم.

heap.cpp

int find_max() {
    return a[1];
}
 
void insert(int val) {
    a[++n] = val;
    for (int x = n; a[x / 2] < a[x]; x /= 2)
        swap(a[x], a[x / 2]);
}
 
int big_child(int x) {
    if (2 * x + 1 <= n && a[2 * x + 1] > a[2 * x])
    return 2 * x + 1;
else if (2 * x <= n)
    return 2 * x;
else
    return -1;
}
 
void delete_max() {
    swap(a[1], a[n--]);
    for (int x = 1; big_child(x) != -1 && a[x] < a[big_child(x)]; x = big_child(x))
        swap(a[x], a[big_child(x)]);
}

• برای پیاده سازی صف‌ اولویت معمولاً از هرم استفاده می‌شود.
• بعضی از انواع پیاده‌سازی الگوریتم دایکسترا یا درخت فراگیر کمینه از هرم استفاده می‌کنند.
• با درج تمام عناصر یک مجموعه در هرم کمینه و استخراج ریشه به طور مکرر، می‌توان اعضای مجموعه را مرتب کرد. به این الگوریتم، مرتب‌سازی هرمی می‌گویند.