1. المعرفة الأساسية
يشير ما نسميه عادة الكومة إلى كومة ثنائية ، والتي تسمى أيضًا شجرة ثنائية كاملة أو شجرة ثنائية كاملة تقريبًا. ينقسم الكومة الثنائية إلى أكبر كومة وأصغر كومة.
يشير فرز الكومة إلى خوارزمية فرز مصممة باستخدام بنية بيانات الكومة ، وهو نوع من اختيار الفرز. يمكنك تحديد موقع عناصر الفهرس المحدد بسرعة باستخدام خصائص الصفيف. يمكن للصفائف الحصول مباشرة على عناصر بناءً على الفهرس ، والتعقيد الزمني هو O (1) ، أي الثوابت ، لذلك فهي فعالة للغاية لاكتساب القيمة.
خصائص أقصى كومة هي كما يلي:
خصائص الحد الأدنى للكومة هي كما يلي:
2. خوارزمية الفكر
1. فكرة الخوارزمية عن أكبر كومة هي:
أولاً ، تم دمج R [0 ... N-1] الأولي في أكبر كومة. في هذا الوقت ، هو كومة غير مرتبة. يعد Top Top هو أكبر عنصر ومن ثم يتم تبادل السجل الأخير R [N-1] في المنطقة غير المرتبة. ينتج عن هذا المنطقة الجديدة غير المرتبة R [0 ... N-2] والمنطقة المطلوبة R [N-1] ، وتلبية R [0 ... N-2].
نظرًا لأن أول r [0 ... n-2] قد لا تفي بخصائص الكومة القصوى بعد التبادل ، يتم ضبط أول r [0 ... n-2] إلى أقصى كومة حتى يتم ضبط العنصر الأخير فقط من r [0].
بعد اكتمال الحد الأقصى لفرز الكومة ، فهو في الواقع تسلسل تصاعدي. في كل مرة يتم فيها ضبط الكومة ، يتم الحصول على أكبر عنصر ثم يتم تبادله مع العنصر الأخير من الكومة الحالية. لذلك ، التسلسل النهائي الذي تم الحصول عليه هو تسلسل تصاعدي.
2. فكرة الخوارزمية عن أصغر كومة هي:
أولاً ، تم بناء R [0 ... N-1] في أصغر كومة. في هذا الوقت ، هو كومة غير مرتبة. العنصر العلوي من الكومة هو أصغر عنصر ، ثم يتبادل أعلى r [0] مع آخر r [n-1] من المنطقة غير المرتبة ، وبالتالي الحصول على كومة جديدة غير مرتبة [0 ... n-2] والكوتين المطلوب [n-1] ، ومرضية r [0 ... n-2] .keys> = n-1]
نظرًا لأن أول R [0 ... N-2] قد لا تفي بخصائص الحد الأدنى للكومة بعد التبادل ، يتم ضبط R [0 ... N-2] على الحد الأدنى للكومة حتى يتم ضبط العنصر الأخير فقط من R [0] ويتم فرز الحد الأدنى للكومة. بعد اكتمال ترتيب الحد الأدنى للكومة ، فهو في الواقع تسلسل تنازلي. في كل مرة يتم فيها ضبط الكومة ، يتم الحصول على أصغر عنصر ثم يتم تبادله مع العنصر الأخير من الكومة الحالية غير المرتبة ، وبالتالي فإن التسلسل الذي تم الحصول عليه في ترتيب تنازلي.
نصيحة: إن عملية فرز الكومة هي في الواقع عملية لتوسيع المنطقة المطلوبة باستمرار ، ثم تقليل المنطقة المضطربة باستمرار حتى تكون هناك مناطق مطلوبة فقط.
3. تحليل عملية الفرز
نظرًا لأن الخوارزمية مجردة نسبيًا ، فإننا نوضح هنا مباشرة عملية فرز الكومة عن طريق إعطاء مثال صغير. بعد ذلك ، نستخدم هذا التسلسل غير المرتبة لاستخدام أكبر كومة لفرز الكومة ، والتسلسل الناتج هو التسلسل الصاعد (ASC).
التسلسل غير المرتبة: 89 ، -7،999 ، -89،7،0 ، -888،7 ، -7
الخطوة 1: تهيئة الحد الأقصى للكومة للبناء:
الخطوة 2: تبادل الحد الأقصى لعنصر 999 في الجزء العلوي من الكومة مع العنصر الأخير من المنطقة غير المرتبة ، بحيث يصبح 999 منطقة مرتبة. بعد التبادل ، يصبح -7 أعلى كومة. نظرًا لأن -7 ليس أكبر عنصر في المنطقة غير المرتبة ، فمن الضروري ضبط المنطقة غير المرتبة بحيث تصبح القيمة القصوى 89 في المنطقة غير المرتبة هي أعلى الكومة ، لذلك يتم تبادل -7 و 89. بعد التبادل ، لا تفي الشجرة الفرعية اليمنى البالغة 89 بخصائص أكبر كومة ، لذلك يجب ضبط الشجرة الفرعية الصحيحة على أكبر كومة ، لذلك يجب تبادل -7 مع 0 ، كما هو موضح في الشكل أدناه:
من الشكل ، عندما تبادل -7 ٪ 89 ٪ ، يكون الجزء العلوي من الوبر هو العنصر الأكبر ، لكن الطفل الأيسر من -7 هو 0 والطفل الأيمن هو -888. منذ -7 <0 ، لا تفي العقدة -7 بخصائص الكومة ، لذلك يجب تعديلها. لذلك ، يتم تبادل 0 مع -7.
ثم كرر الخطوة الثانية حتى تصبح منطقة مرتبة.
أخيرًا: ما تم الحصول عليه هو تسلسل تصاعدي
4. تعقيد الوقت
يتكون وقت فرز الكومة بشكل أساسي من الوقت العام لإنشاء الكومة الأولية وضبط الكومة مرارًا وتكرارًا. نظرًا لأن فرز الكومة غير مستقر ، فإن التعقيد الزمني الذي يحصل عليه سيكون أكبر وفقًا للوضع الفعلي ، لذلك لا يمكن أن يستغرق سوى متوسط تعقيد الوقت.
متوسط تعقيد الوقت هو: o (n * log2 (n))
تشمل العمليات المستهلكة للوقت لفرز الكومة: الكومة الأولي + التعديل المتكرر للكومة ، والتعقيد الزمني كما يلي:
1. بناء الكومة الأولي: ستقارن كل عقدة أولية وتبادلها مع العقد الطفل اليسرى واليمين لمدة تصل إلى مرتين ، وبالتالي فإن التعقيد مرتبط بعدد العقد الأصل. استنادًا إلى 2x <= n (x هو عدد المرات التي يمكن طي عناصر n إلى النصف ، أي عدد العقد الأصل) ، يتم الحصول عليها x = log2n. وهذا هو ، يا (log2n)
2. التعديل المتكرر للكومة: نظرًا لأن نتائج مقارنة الصفيف يتم تسجيلها أثناء تهيئة الكومة ، فإن نوع الكومة ليس حساسًا لترتيب صفيف التسلسل الأصلي ، وأفضل موقف مشابه لأسوأ الحالات. يجب استخراج العنصر العلوي كومة N-1 مرات. في كل مرة يتم فيها أخذ عنصر أعلى الكومة ، يجب إعادة بناء الكومة (O (كومة إعادة بناء) <o (كومة أولية)). أقل من O (N-1) * O (log2n)
الاستخدام الموصى به:
نظرًا لأن عدد مرات تهيئة الكومة تحتاج إلى مقارنة ، فإن فرز الكومة أكثر ملاءمة للحالات التي يكون فيها حجم البيانات كبيرًا جدًا (مليون بيانات أو أكثر). نظرًا لأن الفرز السريع الفعال يعتمد على التنفيذ المتكرر ، يحدث خطأ في التدفق المكدس عندما يكون حجم البيانات كبيرًا جدًا.
5. رمز عينة جافا
Heapsort {private static int [] sort = new int [] {1،0،10،20،3،5،6،4،9،8،12 ، 17،34،11} ؛ public static void main (string [] args) {buildMaxHeapify (sort) ؛ Heapsort (النوع) ؛ طباعة (فرز) ؛ } private static void buildmaxheapify (int [] data) {// فقط أولئك الذين ليس لديهم أطفال يحتاجون إلى إنشاء أقصى كومة ، ابدأ من آخر عقدة الوالدين int startIndex = getParentIndex (data.length-1) ؛ // إنشاء أقصى كومة من النهاية ، وهي الكومة الصحيحة (int i = startIndex ؛ }}/***إنشاء أقصى كومة***@paramdata*@paramheapsize يتطلب حجم الكومة القصوى ، والذي يتم استخدامه بشكل عام في الفرز ، لأنه يتم وضع القيمة القصوى في النهاية ، لم تعد النهاية مصنفة كأقصى قدر من الكومة (int ، النقطة الحالية مع العقد الطفل الأيسر واليمين int int = getChildleftIndex (index) ؛ int right = getChildRightIndex (index) ؛ int أكبر = فهرس ؛ if (left <heapsize && data [index] <data [left]) {marger = left ؛ } if (right <heapsize && data [الأكبر] <data [right]) {الكبير = يمين ؛ } // بعد الحصول على أقصى قيمة ، قد تحتاج إلى تبادلها. إذا تم تبادلها ، فقد لا يكون أطفالها أكبر كومة. يجب تعديله إذا (الأكبر! = فهرس) {int temp = data [index] ؛ البيانات [الفهرس] = البيانات [الأكبر] ؛ البيانات [الأكبر] = درجة الحرارة ؛ maxheapify (البيانات ، الكثافة ، الأكبر) ؛ }} /***الفرز ، يتم وضع القيمة القصوى في النهاية. على الرغم من أن البيانات هي أكبر كومة ، إلا أنها تصبح تدريجية بعد الفرز * * *@paramdata */private static void Heapsort (int [] data) {// exchange with the head في النهاية ، اضبط الحد الأقصى للكومة بعد التبادل (int i = data.length-1 ؛ i> 0 ؛ i-) {int temp = data data [0] ؛ البيانات [0] = البيانات [i] ؛ البيانات [i] = temp ؛ maxheapify (البيانات ، i ، 0) ؛ }} / ** *paramCurrent *@return * / private static int getParentIndex (int current) {return (current-1) >> 1 ؛ } / ** *تقدم وضع عقدة الطفل الاهتمام إلى أقواس ، وأولوية الإضافة أعلى * * *@paramcurrent *@return * / private static int getChildleftIndex (int current) {return (current << 1) +1 ؛ } / ** *موضع عقدة الطفل الأيمن * *@paramcurrent *@return * / private static int getChildRightIndex (int current) {return (current << 1) +2 ؛ } print private static void print (int [] data) {int pre = -2 ؛ لـ (int i = 0 ؛ i <data.length ؛ i ++) {if (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1) ؛ system.out.println () ؛ } system.out.print (data [i]+"|") ؛ }}/** *logo with base 2 * *@paraparam *@return */private static double getLog (double param) {return math.log (param) /math.log (2) ؛ }}