[PHP] Prinzip und Implementierungscode der Heap-Sortierung

Der Hauptinhalt dieses Artikels ist die Verwendung von PHP zur Implementierung der Heap-Sortierung, die einen gewissen Referenzwert hat. Interessierte Freunde können mehr darüber erfahren.

1. Heap (binärer Heap): Er kann als vollständiger Binärbaum betrachtet werden. Mit Ausnahme der untersten Ebene ist jede Ebene voll, sodass der Heap Arrays verwenden kann .um darzustellen, dass jeder Knoten einem Element im Array entspricht

2. Bei gegebenem Index eines Knotens kann der Index des übergeordneten Knotens berechnet werden (i)=floor(i/2) left(i)=2i right=2i+1
3. Maximaler Heap und minimaler Heap, maximaler Heap: der Wurzelknoten ist der Maximalwert, minimaler Heap: der Wurzelknoten Punkt ist der Mindestwert

4. Bei der Heap-Sortierung wird die maximale Anzahl oben aus dem maximalen Heap herausgenommen, der verbleibende Heap weiter an den maximalen Heap angepasst und herausgenommen Erneut die maximale Anzahl an der Spitze des Heaps, bis Es gibt nur ein Ende für die verbleibende Anzahl

5. Maximale Heap-Anpassung (behalten Sie den maximalen Heap bei, der untergeordnete Knoten ist immer kleiner als der übergeordnete Knoten); einen maximalen Heap erstellen (ein Array in ein Array des maximalen Heaps anpassen); Heap-Sortierung (maximalen Heap erstellen, austauschen, maximalen Heap beibehalten)

maxHeapify (array,index,heapSize) //最大堆调整
    iMax,iLeft,iRight
    while true
        iMax=index;iLeft=2*index+1;iRight=2*index+2
        如果根结点小于左右子树里结点值,就交换一下这两个值
        利用第三方变量,交换下两个值
buildMaxHeap(array) //创建最大堆,把一个数组调整成最大堆的数组
    iParent=floor((size-1)/2)
    for i=iParent;i>=0;i--
        maxHeapify (array,i,size)
sort(arr)
    buildMaxHeap(array, heapSize);//创建最大堆
    for (int i = heapSize - 1; i > 0; i--) {
        swap(array, 0, i); //交换第一个和最后一个
         maxHeapify(array, 0, i);//维护最大堆,size小了一个

rrree

Verwandt Tutorials: PHP-Video-Tutorial

Das obige ist der detaillierte Inhalt von[PHP] Prinzip und Implementierungscode der Heap-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!