يتم تقسيم فرز الكومة إلى عمليتين:
1. بناء كومة.
الكومة هي في الأساس شجرة ثنائية تمامًا ويجب أن تفي بما يلي: الكلمات الرئيسية لأي عقدة غير أوراق في الشجرة ليست أكبر من (أو لا تقل عن) الكلمات الرئيسية للطفل (إذا كان هناك) العقدة.
ينقسم الكومة إلى: كومة جذر كبيرة وكومة جذر صغيرة. يتم استخدام الترتيب الصاعد لفرز كومة الجذر الكبيرة ، ويتم استخدام ترتيب تنازلي لفرز كومة الجذر الصغيرة.
إذا كانت كومة جذر كبيرة ، يتم ضبط العقدة ذات القيمة الأكبر على جذر الكومة عن طريق ضبط الوظيفة.
2. احفظ جذر الكومة في الذيل واتصل بوظيفة التعديل للتسلسل المتبقي. بعد اكتمال التعديل ، احفظ الحد الأقصى لأتباع في الذيل -1 (-1 ، -2 ، ... ، -i) ، ثم ضبط التسلسل المتبقي وكرر العملية حتى يتم الانتهاء من الفرز.
نسخة الكود كما يلي:
// ضبط الوظيفة
وظيفة headadjust (عناصر ، نقاط البيع ، لين) {
// احفظ قيمة العقدة الحالية
تبادل var = عناصر [pos] ؛
// حدد موقع العقدة الفرعية على يسار العقدة الحالية
var child = pos * 2 + 1 ؛
// عودية حتى لا يكون هناك أطفال
بينما (الطفل <len) {
// إذا كانت العقدة الحالية تحتوي على عقدة طفل على اليمين وكانت عقدة الطفل الصحيحة أكبر ، فاستخدم عقدة الطفل الصحيحة
// قارن مع العقدة الحالية
if (child + 1 <ly && elements [child] <elements [child + 1]) {
الطفل += 1 ؛
}
// قارن العقدة الحالية مع أكبر عقدة طفل ، إذا كانت القيمة أقل من ، أداء تبادل القيمة ، وتحديد موقع العقدة الحالية بعد البورصة
// على عقدة الطفل
if (عناصر [pos] <elements [child]) {
عناصر [pos] = عناصر [طفل] ؛
POS = طفل ؛
الطفل = pos * 2 + 1 ؛
}
آخر{
استراحة؛
}
عناصر [pos] = مبادلة ؛
}
}
// بناء الكومة
وظيفة buildheap (عناصر) {
// ابدأ من العقدة الأخيرة مع عقدة الطفل ، قارن العقدة بعقدة طفلها ،
// بعد تبادل أكبر رقم مع هذه العقدة ، يتم إجراء نفس عملية التبادل إلى العقدة الأمامية بدورها.
// حتى يتم بناء كومة قمة كبيرة (ترتيب تصاعدي كبير ، ترتيب تنازلي هو قمة صغيرة)
لـ (var i = elements.length/2 ؛ i> = 0 ؛ i-) {
headadjust (العناصر ، i ، elements.length) ؛
}
}
فرز الوظيفة (عناصر) {
// بناء الكومة
Buildheap (عناصر) ؛
// ضبط من نهاية التسلسل
لـ (var i = elements.length-1 ؛ i> 0 ؛ i-) {
// الجزء العلوي من الوبر هو دائمًا العنصر الأكبر ، وبالتالي سيتم تبادل الجزء العلوي من الوبر وعنصر الذيل.
// يتم حفظ العنصر القصوى في النهاية ولا يشارك في التعديلات اللاحقة
تبادل var = عناصر [i] ؛
عناصر [i] = عناصر [0] ؛
عناصر [0] = مبادلة ؛
// إجراء تعديلات ، اضبط العنصر الأقصى إلى أعلى الكومة
headadjust (عناصر ، 0 ، i) ؛
}
}
var elements = [3 ، 1 ، 5 ، 7 ، 2 ، 4 ، 9 ، 6 ، 10 ، 8] ؛
console.log ('قبل:' + عناصر) ؛
فرز (عناصر) ؛
console.log ('بعد:' + عناصر) ؛
كفاءة:
تعقيد الوقت: أفضل: O (Nlog2n) ، الأسوأ: O (Nlog2n) ، المتوسط: O (Nlog2n).
تعقيد الفضاء: O (1).
الاستقرار: غير مستقر