Heap
হিপ
Complete binary tree যেখানে প্রতিটা parent সন্তানের চেয়ে ছোট (min-heap) বা বড় (max-heap) — array-তে থাকে, root-এ extreme element।
also: binary heap, min-heap, max-heap
Pointer লাগে না — complete tree array-তে perfect বসে:
parent(i) = (i−1)/2 left(i) = 2i+1 right(i) = 2i+2দুইটা মূল operation, দুটোই O(log n):
| Operation | কাজ |
|---|---|
| sift-up | শেষে বসানো element-কে উপরে তোলা (insert) |
| sift-down | নতুন root-কে নিচে নামানো (extract-min/max) |
মজার ব্যাপার: nটা element দিয়ে bottom-up build-heap O(n)-এ হয় — nটা আলাদা insert (O(n log n)) না করেও।
Heap-ordered মানে sorted নয় — শুধু parent-child relation জানা; sibling-দের মধ্যে কোনো নিয়ম নেই।