از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
مرتب‌سازی هیپ در جاوا اسکریپت در این راهنما، مرتب‌سازی هیپ را بررسی می‌کنیم – نظریه پشت آن و روش پیاده‌سازی مرتب‌سازی هیپ در جاوا اسکریپت. ما با ساختار داده ای که بر اساس آن است شروع خواهیم کرد روی (پیش‌گویی عظیم در اینجا: این یک پشته است!)، روش انجام عملیات روی آن ساختار داده و روش آن داده ها…
سرفصلهای مطلب
معرفی
در این راهنما به بررسی خواهیم پرداخت مرتب سازی هیپ – تئوری پشت آن و روش پیاده سازی مرتب سازی هیپ در جاوا اسکریپت.
ما با ساختار داده ای که بر اساس آن است شروع خواهیم کرد روی (پیش‌گویی عظیم در اینجا: این یک است پشته!)، روش انجام عملیات روی آن ساختار داده و اینکه چگونه می توان از آن ساختار داده به عنوان ابزاری برای یک الگوریتم مرتب سازی کارآمد استفاده کرد.
ساختار داده ها و الگوریتم های مرتب سازی مفاهیم اصلی در برنامه نویسی هستند. یک برنامه کامپیوتری به طور مداوم با مجموعه داده های بزرگ، بازیابی و تزریق داده ها در حالت تهوع سروکار دارد. روشی که ما این مجموعه داده ها را سازماندهی می کنیم و عمل می کنیم روی آنها از اهمیت زیادی برخوردار هستند زیرا مستقیماً بر سهولت و سرعت تعامل کاربر با برنامه های ما تأثیر می گذارد.
یک الگوریتم مرتب سازی بر اساس ارزیابی می شود روی دو ویژگی: زمان و فضا الگوریتم به عنوان تابعی از اندازه مجموعه داده استفاده می کند. اینها به عنوان معروف هستند پیچیدگی زمانی و پیچیدگی فضا به ترتیب، و به ما این امکان را می دهد که در سناریوهای متوسط و بهترین حالت، الگوریتم ها را در برابر یکدیگر قرار دهیم.
مرتب سازی هیپ به عنوان یک الگوریتم کارآمد با میانگین پیچیدگی زمانی در نظر گرفته می شود θ(n log(n)).
اگرچه الگوریتم‌های دیگری وجود دارد که در سناریوی متوسط عملکرد بهتری از مرتب‌سازی هیپ دارند، اهمیت آن متکی است روی قدرت آن برای عملکرد با همان کارایی در بدترین سناریو که در بهترین حالت انجام می‌دهد، به آن یک زمان اجرا پایدار در مجموعه داده‌های مختلف می‌دهد، در حالی که برخی از الگوریتم‌ها ممکن است از الگوریتم‌های بزرگ یا کوچک رنج ببرند. روی مکانیسم زیربنایی آنها
مرتب سازی هیپ در جاوا اسکریپت
Heap Sort یک الگوریتم مرتب‌سازی در محل، ناپایدار و مبتنی بر مقایسه است.
به ساختارهای داده کمکی نیاز ندارد – داده ها را مرتب می کند درجا و داده های اصلی را تحت تاثیر قرار می دهد (درجا). آن را حفظ نمی کند نظم نسبی یا عناصر برابر. اگر دو عنصر با یک مقدار در یک مجموعه مرتب نشده دارید، ممکن است ترتیب نسبی آنها در مجموعه مرتب شده تغییر کند (یا ثابت بماند)ناپایدار). در نهایت، عناصر برای یافتن ترتیب آنها با یکدیگر مقایسه می شوند (مبتنی بر مقایسه).
اگرچه Heap Sort در جای خود قرار دارد (به ساختار داده کمکی نیاز ندارد)، برای اینکه پیاده سازی کمی واضح باشد، یک آرایه اضافی را در حین مرتب سازی به کار می گیریم.
مکانیسم زیربنایی Heap Sort نسبتاً ساده است و برخی حتی آن را “” می نامند.مرتب سازی انتخاب بهبود یافته”.
اگر می‌خواهید درباره مرتب‌سازی انتخابی بیشتر بخوانید، مرتب‌سازی انتخابی ما را در جاوا اسکریپت بخوانید!
با تبدیل آرایه مرتب نشده به a شروع می شود پشته – یا الف max-heap یا min-heap. در مورد max-heap، هر یک از والدین ارزش بیشتری نسبت به فرزندان خود دارند، که باعث می شود root عنصر بزرگترین در میان پشته و بالعکس.
Heap Sort متکی است روی این وضعیت پشته.
در هر تکرار، الگوریتم حذف می کند root از پشته و آن را به یک آرایه خالی فشار می دهد. پس از هر حذف، پشته خود را بازیابی می کند و دومین عنصر بزرگ (یا دومین کوچکترین) خود را تا root برای حفظ وضعیت پشته آن این process نیز شناخته می شود انبوه کننده و اغلب می بینید که مردم به روش هایی برای انجام این کار اشاره می کنند انباشته کردن.
مرتب‌سازی هیپ به تغییر مکان جدید ادامه می‌دهد root عناصر در آرایه مرتب شده تا زمانی که هیچ کدام باقی نماند.
استفاده از max-heap در این روش منجر به ایجاد آرایه ای با عناصر به ترتیب نزولی می شود. برای اینکه آرایه به ترتیب صعودی باشد، باید min-heap را انتخاب کرد.
این نوع خود مرتب‌سازی و حذف انتخابی یادآور Selection Sort (بدون قسمت خود مرتب‌سازی) است، از این رو افراد موازی ترسیم می‌کنند.
a چیست پشته?
هیپ یک ساختار داده درخت مانند است. نوع پشته ای که ما برای اهداف خود استفاده خواهیم کرد، یک درخت باینری خواهد بود (ساختار داده ای که شبیه یک شاخه درخت است و باید با یک شاخه شروع شود. node و اگر منشعب شود، حداکثر دو جانشین از هر کدام مجاز است node). در حالی که انواع کمی از هپ وجود دارد، دو ویژگی متمایز از یک پشته وجود دارد:
- یک پشته باید باشد کامل، به این معنی که هر سطح از درخت باید از چپ به راست پر شود و یکی مجاز نیست سطح دیگری از درخت را بدون پر کردن تمام گره های ممکن باقی مانده ایجاد کند. روی آخرین سطح
- هر یک node باید مقداری بزرگتر یا مساوی با (در مورد کوچکتر کوچکتر یا مساوی) ارزش هر یک از فرزندان خود داشته باشد. به این وضعیت “هپ” می گویند.
نگاشت یک Heap به یک آرایه
آنچه تا به اینجا به صورت توده ای تعریف و ترسیم کرده ایم، صرفاً یک نمودار، مجموعه ای از دایره ها و خطوط است. برای استفاده از این ساختار در یک برنامه کامپیوتری مبتنی بر جاوا اسکریپت، باید آن را در یک آرایه یا یک لیست دوباره کار کنیم.
خوشبختانه، این یک عملیات نسبتاً ساده است که در وهله اول از روش ساختن پشته تقلید می کند. ما عناصر پشته را می خوانیم و به همان ترتیبی که آنها را در پشته قرار داده ایم، به آرایه ای تغییر می دهیم: از چپ به راست و تراز به سطح.
نمونه ای از یک پشته و همتای آرایه آن، پس از این تغییر:
به این ترتیب، نه تنها می‌توانیم یک پشته را در کد بیان کنیم، بلکه قطب‌نمایی نیز به دست می‌آوریم که با آن می‌توانیم درون آن پشته حرکت کنیم. ما می توانیم سه معادله را کسر کنیم، با توجه به هر کدام nodeایندکس ما را به محل والد و فرزندان راست و چپ آن در داخل آرایه نشان می دهد:
ایجاد Heap در جاوا اسکریپت
اکنون که تعریف دقیقی از heap ارائه شده است، می توانیم آن را به عنوان یک کلاس جاوا اسکریپت پیاده سازی کنیم.
در این راهنما، ما یک max-heap را ایجاد و استفاده می کنیم. از آنجایی که تفاوت بین max-heap و min-heap بی اهمیت است و بر منطق کلی الگوریتم مرتب سازی Heap تأثیری نمی گذارد، اجرای min-heap و بنابراین ایجاد یک ترتیب صعودی از طریق مرتب سازی heap یک موضوع است. تغییر عملگرهای مقایسه
بیایید جلو برویم و a را تعریف کنیم MaxHeap کلاس:
class MaxHeap{
constructor(){
this.heap = ();
}
parentIndex(index){
return Math.floor((index-1)/2);
}
leftChildIndex(index){
return (2*index + 1);
}
rightChildIndex(index){
return (2*index + 2);
}
}
در MaxHeap کلاس، سازنده ای تعریف کرده ایم که یک آرایه خالی را مقداردهی اولیه می کند. بعد روی، ما توابع اضافی برای پر کردن یک پشته در داخل این آرایه ایجاد خواهیم کرد.
با این حال، در حال حاضر فقط توابع کمکی ایجاد کرده‌ایم که نمایه والدین و فرزندان یک مورد خاص را برمی‌گرداند. node.
درج عناصر به یک پشته
هر زمان که یک عنصر جدید در یک پشته قرار می گیرد، در کنار سمت راست قرار می گیرد node روی سطح پایین (آخرین فضای خالی در نمایش آرایه) یا، اگر سطح پایین از قبل پر است، در سمت چپ node از یک سطح جدید در این سناریو، اولین نیاز پشته: کامل بودن درخت، تضمین می شود.
با حرکت رو به جلو، ویژگی heap، که احتمالاً مختل شده است، باید دوباره ایجاد شود. برای انتقال عنصر جدید به محل مناسب خود روی پشته با والد خود مقایسه می شود و اگر عنصر جدید بزرگتر از والد خود باشد، عناصر تعویض می شوند.
عنصر جدید در پشته حباب می شود، در حالی که در هر سطح با والد خود مقایسه می شود تا در نهایت ویژگی heap بازیابی شود:
بیایید این قابلیت را به کلاس MaxHeap که قبلا ایجاد کرده بودیم اضافه کنیم:
swap(a, b) {
let temp = this.heap(a);
this.heap(a) = this.heap(b);
this.heap(b) = temp;
}
insert(item) {
this.heap.push(item);
var index = this.heap.length - 1;
var parent = this.parentIndex(index);
while(this.heap(parent) && this.heap(parent) < this.heap(index)) {
this.swap(parent, index);
index = this.parentIndex(index);
parent = this.parentIndex(index);
}
}
swap() به عنوان یک روش کمکی اضافه می شود تا مقداری افزونگی در کد را ذخیره کنیم زیرا در حین درج عنصر جدید، ممکن است مجبور باشیم این عمل را چندین بار انجام دهیم – عددی بین صفر و ورود (n) (در موردی که عنصر جدید بزرگتر از root از پشته، و ما باید آن را مجبور کنیم از کل درختی که ارتفاع دارد بالا برود ورود به سیستم (تعداد کل عناصر آن) – که به عبارت دیگر الف است مقدار زیادی.
insert() به شرح زیر عمل می کند:
- عنصر داده شده را به
heapبا استفاده از روش جاوا اسکریپت داخلی:push(). - آخرین عنصر را علامت گذاری می کند
heapمانندindexو والد آن به عنوانparent. - در حالی که یک عنصر از پشته در شاخص وجود دارد
parent(this.heap(parent)) و آن عنصر از عنصر در کوچکتر استindex(this.heap(parent) < this.heap(index)،insert()روش می رود روی به swap آن دو (this.swap(parent, index)) و مکان نما خود را یک سطح به سمت بالا حرکت می دهد.
حذف عناصر از پشته
یک پشته فقط اجازه حذف را می دهد root عنصری که پس از آن ما را با یک پشته کاملاً تحریف شده باقی می گذارد. بنابراین، ابتدا باید آن را بازگردانیم درخت دودویی کامل ملک با جابجایی آخرین node از پشته به root. سپس ما نیاز داریم حباب این مقدار نابجا تا زمانی که ویژگی heap به جای خود بازگردد پایین می آید:
delete() {
var item = this.heap.shift();
this.heap.unshift(this.heap.pop());
var index = 0;
var leftChild = this.leftChildIndex(index);
var rightChild = this.rightChildIndex(index);
while(this.heap(leftChild) && this.heap(leftChild) > this.heap(index) || this.heap(rightChild) > this.heap(index)){
var max = leftChild;
if(this.heap(rightChild) && this.heap(rightChild) > this.heap(max)){
max = rightChild
}
this.swap(max, index);
index = max;
leftChild = this.leftChildIndex(max);
rightChild = this.rightChildIndex(max);
}
return item;
}
این delete() روش، که ما در داخل ایجاد می کنیم MaxHeap کلاس به روش زیر عمل می کند:
- این روش با برداشت بزرگترین عنصر آغاز می شود – بنابراین، اولین عنصر در نمایش آرایه پشته. ساخته شده در
shift()متد اولین عنصر آرایه را حذف می کند و عنصر حذف شده را برمی گرداند که سپس آن را در آرایه ذخیره می کنیمitemمتغیر. - آخرین عنصر از
heapاز طریق حذف می شودpop()و در اولین فضای خالی شده قرار می گیردheapاز طریقunshift().unshift()یک روش جاوا اسکریپت داخلی است که به عنوان همتای آن کار می کندshift(). در حالی کهshift()اولین عنصر آرایه را حذف می کند و بقیه عناصر را یک فاصله به عقب منتقل می کند.unshift()یک عنصر را به ابتدای آرایه هل می دهد و بقیه عناصر را یک فاصله به جلو می برد. - برای اینکه بتوانیم جدید را حباب کنیم root به سمت پایین، نشانگر محل آن است که در ابتدا 0 است و دو فرزند آن (
index،rightChild،leftChild) ایجاد می شود. - این
while()حلقه بررسی می کند که آیا فرزند سمت چپ وجود دارد یا خیرindexnode برای اطمینان از وجود سطح دیگری در زیر (هنوز فرزند مناسب را بررسی نکرده است) و اگر هر یک از کودکان در این سطح بزرگتر از node در (index). - اگر شرط داخل حلقه while برقرار باشد، الف
maxمتغیر برای اعلام سمت چپ ایجاد می شود node حداکثر مقداری است که روش تاکنون با آن مواجه شده است. سپس در داخل حلقه، در یکifبند، بررسی می کنیم که آیا فرزند راست وجود دارد یا خیر، و اگر وجود دارد، آیا بزرگتر از فرزند چپی است که ابتدا بررسی کردیم. اگر ارزش فرزند مناسب واقعاً بزرگتر باشد، شاخص آن جایگزین مقدار in می شودmax. - هر کودکی که ارزش بیشتری داشته باشد با والدینش مبادله می شود
this.swap(max, index). - این روش مکان نما خیالی خود را در انتهای حلقه while یک سطح به سمت پایین حرکت می دهد و می رود روی برای اجرای کد در داخل حلقه while بارها و بارها تا زمانی که شرایط آن دیگر برقرار نباشد.
پیاده سازی مرتب سازی هیپ در جاوا اسکریپت
در نهایت، برای دستیابی به آنچه که این راهنما وعده داده است، یک را ایجاد می کنیم heapSort() تابع (این بار خارج از MaxHeap class)، و آرایه‌ای را که می‌خواهیم مرتب کنیم، به آن عرضه کنیم:
function heapSort(arr){
var sorted = ();
var heap1 = new MaxHeap();
for(let i=0; i<arr.length; i++){
heap1.insert(arr(i));
}
for(let i=0; i<arr.length; i++){
sorted.push(heap1.delete());
}
return sorted;
}
این heapSort() آرایه را به عنوان آرگومان مرتب‌سازی می‌کند. سپس، یک آرایه خالی برای قرار دادن نسخه مرتب شده و همچنین یک پشته خالی ایجاد می کند که از طریق آن مرتب سازی انجام می شود.
سپس، heap1 پر از عناصر است arr و یکی یکی حذف می شوند و عناصر حذف شده را به آرایه مرتب شده فشار می دهند. این heap1 با هر حذف خود سازماندهی می شود، بنابراین فقط با فشار دادن عناصر از آن به آرایه مرتب شده، ما را با یک آرایه مرتب شده شبکه می کنیم.
بیایید یک آرایه ایجاد کنیم و این را آزمایش کنیم:
let arr = (1, 6, 2, 3, 7, 3, 4, 6, 9);
arr = heapSort(arr);
console.log(arr);
نتیجه
در این راهنما، ما با ساختار داده های پشته و روش عملکرد مرتب سازی هیپ آشنا شده ایم.
در حالی که سریع‌ترین الگوریتم ممکن نیست، مرتب‌سازی هیپ می‌تواند زمانی سودمند باشد که داده‌ها به طور جزئی مرتب شده باشند یا زمانی که نیاز به یک الگوریتم پایدار وجود دارد.
حتی اگر ما آن را با استفاده از یک ساختار داده اضافی پیاده‌سازی کرده‌ایم، Heap Sort اساساً یک الگوریتم مرتب‌سازی در محل است و به همین دلیل، می‌تواند در مواقعی که استفاده از حافظه مورد توجه است نیز استفاده شود.
منتشر شده در 1403-01-15 02:19:05
