مثيل فرز كومة جافا (كومة أعلى كبيرة ، كومة قمة صغيرة)

يشير فرز الكومة إلى خوارزمية فرز مصممة باستخدام بنية بيانات الكومة. التراص عبارة عن بنية عبارة عن شجرة ثنائية تمامًا تقريبًا وتفي بخصائص التراص: أي أن القيمة الرئيسية أو فهرس العقدة الفرعية أصغر دائمًا من (أو أكبر من) العقدة الأم.

متوسط تعقيد الوقت من نوع الكومة هو (nlogn).

خطوات الخوارزمية:

1. إنشاء كومة H [0..n-1]

2. مبادلة رأس الكومة (الحد الأقصى) وذيل الكومة

3. قلل من حجم الكومة بمقدار 1 و Call Shift_down (0). والغرض من ذلك هو ضبط البيانات العليا للمصفوفة الجديدة إلى الموضع المقابل.

4. كرر الخطوة 2 حتى يكون حجم الكومة 1

كومة:

الكومة هي في الواقع شجرة ثنائية تمامًا ، وأي عقدة غير الأوراق من عقدة غير الأوراق لها تلبي خصائصها: المفتاح [i] <= Key [2i+1] && key [i] <= Key [2i+2] أو Key [i] = key [2i+1] ينقسم الكومة إلى كومة قمة كبيرة وكومة قمة صغيرة. يُطلق على مفتاح مرضي [i]> = المفتاح [2i+1] يُطلق على مفتاح مرضي [i] <= Key [2i+1] && key [i] <= Key [2i+2] كومة قمة صغيرة. من الخصائص المذكورة أعلاه ، يمكننا أن نرى أن الكلمات الرئيسية الموجودة في الجزء العلوي من الكومة العليا الكبيرة هي بالتأكيد أكبر الكلمات الرئيسية ، والكلمات الرئيسية الموجودة في الجزء العلوي من الكومة الصغيرة هي أصغر من جميع الكلمات الرئيسية.

فكرة فرز الكومة:

ميزة أكبر الكلمة الرئيسية (الحد الأدنى للكلمة الرئيسية) التي يتم تسجيلها في الجزء العلوي من الكومة العليا الكبيرة (كومة أعلى صغيرة) تجعل من السهل تحديد أكبر سجل (سجل الحد الأدنى) من الاضطراب في كل مرة. الفكرة الأساسية هي (كومة أعلى كبيرة): 1) بناء التسلسل الأولي للكلمات الرئيسية المراد فرزها (R1 ، R2 ... .RN) في كومة كبيرة كبيرة ، وهي المنطقة الأولية المضطربة ؛ 2) تبادل العنصر العلوي للكومة R [1] مع العنصر الأخير R [n] ، ثم الحصول على منطقة مضطربة جديدة (R1 ، R2 ، ... RN-1) ومنطقة جديدة مرتبة (RN) وتلبية R [1،2 ... N-1] <= r [n] ؛ 3) نظرًا لأن الكومة الجديدة العلوية R [1] بعد التبادل قد تنتهك خصائص الكومة ، فمن الضروري ضبط المنطقة المضطربة الحالية (R1 ، R2 ، ... RN-1) إلى كومة جديدة ، ثم تبادل R [1] مع العنصر الأخير من المنطقة المضطربة مرة أخرى للحصول على منطقة جديدة مضطربة (R1 ، R2 ... كرر هذه العملية حتى يكون عدد العناصر في المنطقة المطلوبة N-1 ، ويتم الانتهاء من عملية الفرز بأكملها. عملية التشغيل هي كما يلي: 1) تهيئة الكومة: بناء r [1..n] كوسيلة ؛ 2) تبادل العنصر العلوي الكومة R [1] للمنطقة غير المرتبة الحالية مع آخر سجل في الفاصل الزمني ، ثم اضبط المنطقة الجديدة غير المرتبة على كومة جديدة. لذلك ، بالنسبة لفرز الكومة ، فإن العمليتين الأكثر أهمية هما بناء الكومة الأولية وضبط الكومة. في الواقع ، فإن بناء الكومة الأولية هو في الواقع عملية لضبط الكومة ، ولكن بناء الكومة الأولية هو ضبط جميع العقد غير الورقية.

مثال على التوضيح

بالنظر إلى صفيف تشكيل A [] = {16،7،3،20،17،8} ، فرز الكومة. أولاً ، قم بإنشاء شجرة ثنائية كاملة بناءً على عنصر الصفيف ، واحصل عليها

ثم تحتاج إلى بناء الكومة الأولية ، ثم بدء التعديل من آخر عقدة غير الأوراق. عملية التعديل هي كما يلي:

بعد تبادل 20 و 16 ، 16 يسبب 16 لعدم الوفاء بخصائص الكومة ، لذلك يجب تعديلها.

هذا يعطي الكومة الأولية.

عندما يتم ضبطه أولاً ، يصبح كومة كبيرة.

أي أن كل تعديل هو تحديد أكبر المعدل من العقدة الأصل ، وعقدة الطفل اليسرى ، والعقدة الطفل الصحيحة للتبادل مع العقدة الأصل (بعد التبادل ، قد تتسبب عقدة الطفل في تبادل العقدة الطفل لعدم تلبية طبيعة الكومة ، لذلك يجب ضبط عقدة الطفل مرة أخرى بعد التبادل). مع الكومة الأولية ، يمكنك فرزه.

في هذا الوقت ، يقع 3 في الجزء العلوي من الوبر والخصائص ليست مليئة بالوك. تحتاج إلى ضبط ومتابعة ضبط.

وبهذه الطريقة ، يكون الفاصل الزمني بأكمله بالفعل منظمًا. من العملية أعلاه ، يمكننا أن نرى أن فرز الكومة هو في الواقع نوع من فرز الاختيار ، فرز اختيار الأشجار. ولكن من أجل تحديد الطلب مباشرة ، من أجل تحديد الحد الأقصى للسجل من R [1 ... n] ، يجب مقارنة مرات N-1 ، ثم تحديد السجل القصوى من R [1 ... N-2] ، يجب مقارنة N-2 مرات. في الواقع ، تم إجراء العديد من مقارنات N-2 هذه في مقارنات N-1 السابقة ، ويستخدم فرز اختيار الأشجار فقط خصائص الشجرة لتوفير بعض نتائج المقارنة السابقة ، وبالتالي يمكن تقليل عدد المقارنات. بالنسبة لتسلسلات الكلمات الرئيسية ، في أسوأ الأحوال ، تحتاج كل عقدة إلى مقارنة Log2 (n) مرات ، وبالتالي فإن أسوأ تعقيد وقت الحالة هو nlogn. يعد نوع الكومة نوعًا غير مستقر وهو غير مناسب للفرز مع عدد أقل من السجلات. لقد تم وصف الكثير أعلاه. باختصار ، فإن الممارسة الأساسية لفرز الكومة هي: أولاً ، استخدم البيانات الأصلية لإنشاء كومة كبيرة (صغيرة) كمساحة أصلية غير مرتبة ، وبعد ذلك ، في كل مرة يتم فيها إخراج العنصر العلوي الكومة ووضعه في المنطقة المطلوبة. نظرًا لأن العنصر العلوي من الكومة ، وضعنا العنصر الأخير في الكومة في الجزء العلوي من الكومة ، لذلك يتم تدمير خصائص الكومة. نحتاج إلى إعادة ضبط الكومة والمتابعة في الأوقات ، ثم يتم وضع عناصر n في المنطقة غير المرتبة في المنطقة المطلوبة ، ويتم الانتهاء من عملية الفرز.
(مكدس البناء من أسفل إلى أعلى)

التطبيق العملي:

في الممارسة العملية ، نقوم بإجراء فرز الكومة للحصول على الحد الأقصى أو الحد الأدنى من القيمة في ظل ظروف معينة. على سبيل المثال: 10 القيم القصوى يجب العثور عليها بين 100 رقم. لذلك ، نحدد كومة من الحجم 10 ، وننشئ البيانات العشرة الأولى في 100 كومة قمة صغيرة (الجزء العلوي من الكومة) ، ثم نقارنها بأعلى الكومة من البيانات الحادية عشرة في 100 بيانات. إذا كان الجزء العلوي من الكومة أصغر من البيانات الحالية ، يتم ظهر الجزء العلوي من الكومة ، واضغط على البيانات الحالية في الجزء العلوي من الكومة ، ثم نقل البيانات من أعلى الكومة إلى موضع معين.

شفرة:

 اختبار الفئة العامة test0 {static int [] arr ؛ // heap array ، صفيف صفيف صالح test0 (int m) {arr = new int [m] ؛} static int m = 0 ؛ static int size = 0 ؛ {16،4،5،9،1،10،11،12،13،14،2،2،3،6،11111،222،333،555،66،67،54} ؛ int [10] ؛ if (size <arr.length) {arr [size] = v ؛ add_sort (size) ؛ // add_sort1 (size) ؛ size ++ ؛} else {arr [0] = v ؛ add_sort1 (0) ؛}} printsmall () {for (int i = 0 ؛ i <size ؛ i ++) {system.out.println (arr [i]) ؛}} public void del () {size-؛ arr [0] = arr [9] ؛ add_sort1 (0) ؛} public void small (int الفهرس) {if (m <arr.length) {add_sort (index) ؛ m ++ ؛} else {add_sort1 (index) ؛ m ++ ؛ الطفل الأيسر*إذا كان آخر واحد في الصفيف حتى ، فهو الطفل المناسب إذا كانت عقدة الطفل أكبر من العقدة الأصل ، يتم إجراء تبادل القيمة. إذا كان الطفل الأيمن أكبر من الطفل الأيسر ، فسيتم إجراء تبادل القيمة**/int par ؛ if (index! = 0) {if (index ٪ 2 == 0) {par = (index-1)/2 ؛ if (arr [index] <arr [par]) {swap (arr ، index ، par) ؛ dex] <arr [par]) {swap (arr ، index ، par) ؛ ad add_sort (par) ؛}} آخر {par = index/2 ؛ if (arr [index] <arr [par]) {swap (ord ، index ، par) ؛ add_sort (par) ؛} par*2+1) ؛ if (arr [index] <arr [par]) {swap (arr ، index ، par) ؛} add_sort (par) ؛}}}} public void add_sort1 (int index) {// add ad head small/*add top down*ext the the child ind in in in in exter ، int*؛ max = 0 ؛ if (left <10 && arr [left] <arr [index]) {max = left ؛} else {max = index ؛} if (right <10 && arr [right] <arr [max]) {max = right ؛} if (max! = index) {swap (arr ، max ، index) ؛ add_sort1 ؛ استيراد java.util.scanner ؛ الفئة العامة main_test0 {public static void main (String args []) {16،4،5،9،1،10،11،12،13،14،2،2،3،6،7،8} ؛ for (int i = 0 ؛ i <a.length ؛ i ++) {test.addtosmall (a [i]) ؛} test.printsmall () ؛ test.del () ؛

مثال فرز كومة Java أعلاه (كومة أعلى كبيرة ، كومة صغيرة صغيرة) هو كل المحتوى الذي أشاركه معك. آمل أن تتمكن من إعطائك مرجعًا وآمل أن تتمكن من دعم wulin.com أكثر.