هرم (ساختمان داده)
From Wikipedia, the free encyclopedia
در علوم رایانه، هرم (Heap) داده ساختاری است که بر اساس درختها پیادهسازی میشود. هرم یک داده ساختار بهینه برای پیادهسازی یک داده گونه انتزاعی(abstract data type) به نام صف اولویت دار است. هرمها میتوانند به شکلهای مختلفی پیادهسازی شوند. یکی از رایجترین پیادهسازیها، هرم دودویی است که با استفاده از درخت دودویی مدل میشود.
هرم دودویی دو نوع دارد:
- هرم بیشینه (Max heap)
- هرم کمینه (Min heap)
برای الگوریتم مرتبسازی هرمی از هرم بیشینه و برای پیادهسازی صف اولویت دار معمولاً از هرم کمینه استفاده میشود.[1]
در هر دو نوع، مقادیر گرهها از خاصیت هرم پیروی میکنند. خاصیت هرم بیشینه این است که به ازای هر گره، مقدار موجود در والدش (parent) در صورت وجود بزرگتر مساوی با مقدار آن گره است؛ بنابراین عنصر بیشینه در ریشه درخت (root) قرار دارد.
خاصیت هرم کمینه، برعکس هرم بیشینه است به این صورت که به ازای هر گره، مقدار موجود در والدش (parent) در صورت وجود کوچکتر مساوی با مقدار آن گره است؛ بنابراین عنصر کمینه در ریشه درخت (root) قرار دارد.
در هرمهای دودویی روابطی بین اندیس هر گره (i)، والد ((parent(i)، فرزند چپ ((left(i) و فرزند راست ((right(i) آن در آرایه مرتب شده وجود دارد:
- [ Parent(i) = arr[ (i-1) / 2
- [ Left(i) = arr[ (2*i) + 1
- [ Right(i) = arr[ (2*i) + 2
اگر هرم را به چشم یک درخت ببینیم ارتفاع ( height ) برای هر گره ، اندازه طولانیترین مسیر نزولی از آن گره تا یکی از برگها و ارتفاع هرم معادل با ارتفاع گره ی ریشه خواهد بود .بنابراین در هرمی دودویی متشکل از n عنصر ، ارتفاع هرم ( Θ( log n است.[2] همچنین عمق (depth) هر گره برابر با طول مسیر از آن گره تا گرهٔ ریشه و عمق هرم معادل با عمق آخرین لایه از برگها خواهد بود.
توابعی که بر روی هرمها پیادهسازی میشوند عبارتند از: