Heap Sort

การเรียงลำดับข้อมูลแบบฮีป (Heap Sort)

     การเรียงข้อมูลแบบฮีป คือการจัดเรียงข้อมูลโดยอาศัยหลักการ หรือโครงสร้างของไบนารีทรี (Binary Tree) มาเป็นกระบวนการหลักในการทางาน ซึ่งวิธีการเรียงลาดับแบบไบนารีทรีนี้ เป็นวิธีที่ดีที่สุดของการเรียงลาดับข้อมูล ทั้งยังสามารถทางานได้ดีในข้อมูลที่มีความซับซ้อนมากๆ แม้ว่าค่าเฉลี่ยของการทางานอาจจะไม่ได้เร็วที่สุดก็ตาม (ในกรณีที่มีปัจจัยอื่น ๆ คงที่) แต่คุณสมบัติของฮีปก็ยังสามารถเรียงลาดับชุดข้อมูลที่มีขนาดใหญ่ และซับซ้อนได้ดีกว่าการเรียงข้อมูลแบบอื่นจากที่ได้กล่าวมาในข้างต้นถึงกระบวนการทางานของฮีป ซึ่งการอาศัยหลักการของไบนารีทรีในการดาเนินการนั้น หากจะนับว่าโครงสร้างดังกล่าวเป็นฮีปทรี (Heap Tree) ได้นั้นต้องอยู่ภายใต้เงื่อนไขดังต่อไปนี้

1. ในทุก ๆ ระดับของฮีปทรี นั้นจะสามารถแตกสาขาออกไปได้ทั้งซ้ายและขวา เริ่มจากการแตกสาขาออกไปทางซ้ายก่อนแล้วค่อยสลับไปทางขวา และจะต้องมีโหนดให้ครบทั้งสองด้านก่อน จึงจะสามารถแตกโหนดในระดับต่อไปได้
2. โหนดในระดับสูงกว่า หรือคีย์โหนดจะต้องอยู่ในลักษณะของโหนดตัวแม่ กล่าวคือจะต้องมีค่ามากกว่าโหนดลูกเสมอ
     อัลกอริทึมการเรียงลำดับข้อมูลแบบHeap Sortได้มีการนำวิธีการเรียงลำดับข้อมูลแบบSelection  Sort มาปรับปรุงให้มีประสิทธิภาพดียิ่งขึ้นโดยHeap  Sort จะเริ่มต้นทำงานจากอาร์เรย์ที่มีการจัดเรียงลำดับข้อมูลแบบฮีพ  ซึ่งคุณสมบัติสำคัญของฮีพทรีก็คือ รูทโหนดจะมีค่ามากที่สุด  และในการแทนฮีพทรีในอาร์เรย์  ค่าที่มากที่สุดจะอยู่ที่ตำแหน่งแรกดังนั้นเราจะนำค่าที่มากที่สุดในตำแหน่งแรกสลับกับค่าสุดท้ายของฮีพและถือว่าโหนดสุดท้ายนี้ได้หลุดออกจากฮีพทรีแล้ว จากนั้นสมาชิกหรือข้อมูลส่วนที่เหลือก็จะมีการรีฮีพโครงสร้างใหม่ ซึ่งค่าที่มากที่สุดก็จะอยู่ที่ตำแหน่งแรกเช่นเดิมและจะดำเนินการเช่นนี้ไปจนกระทั่งได้จัดการกับข้อมูลทั้งหมดในฮีพก็จะได้ข้อมูลที่จัดเรียงเรียบร้อยอย่างสมบูรณ์พิจารณาจากรูปที่ซึ่งแสดงขั้นตอนการเรียงลำดับข้อมูลแบบ Heap Sort  จะเห็นได้ว่าในรอบแรกค่าที่มากที่สุดคือ  78  ซึ่งอยู่บนท็อปของฮีพ  หรืออยู่ในตำแหน่งแรกของอาร์เรย์  โดยเราจะทำการเปลี่ยนตำแหน่งนี้กับสมาชิกสุดท้ายที่อยู่ในฮีพซึ่งค่ามากที่สุดที่ย้ายมาท้ายลิสต์นี้จะเป็นส่วนที่จัดเรียงแล้ว จากนั้นก็จะนำสมาชิกส่วนที่เหลือมาจัดโครงสร้างฮีพทรี  เพื่อให้โหนดที่มีค่าสูงสุดอยู่ตำแหน่งแรก และจะดำเนินการเช่นนี้ไปจนกระทั่งหมดข้อมูลในฮีพทรี



Algorithms Heap Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<script>
var a = [4, 1, 3, 5, 2, 6];
console.log(a);
heapSort(a);
console.log(a);
 
function swap(a, i, j) {
    var tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}
 
function max_heapify(a, i, length) {
    while (true) {
        var left = i*2 + 1;
        var right = i*2 + 2;
        var largest = i;
 
        if (left < length && a[left] > a[largest]) {
            largest = left;
        }
 
        if (right < length && a[right] > a[largest]) {
            largest = right;
        }
 
        if (i == largest) {
            break;
        }
 
        swap(a, i, largest);
        i = largest;
    }
}
 
function heapify(a, length) {
    for (var i = Math.floor(length/2); i >= 0; i--) {
        max_heapify(a, i, length);
    }
}
 
function heapSort(a) {
    heapify(a, a.length);
    for (var i = a.length - 1; i > 0; i--) {
        swap(a, i, 0);
        max_heapify(a, 0, i-1);
    }
}
</script>


ไม่มีความคิดเห็น:

แสดงความคิดเห็น

สมัครสมาชิก: บทความ (Atom)