Classic Algorithm Learning - Heap Sort_PHP Tutorial

Classic Algorithm Learning - Heap Sort

Heap sorting is a slightly more troublesome sorting than other sorting. It is a selection sort that takes advantage of the properties of the heap. The heap is actually a complete binary tree. As long as the key of any non-leaf node is not greater than or not less than its left and right child nodes, a heap can be formed. Heaps are divided into large top piles and small top piles. It can be seen from the above properties that the keyword at the top of the big heap is the largest of all keywords, and the keyword at the top of the small heap is the smallest of all keywords. Heap sort, like quick sort, is an unstable sort. Sample code uploaded to: https://github.com/chenyufeng1991/HeapSort

The idea of ​​heap sorting: taking advantage of the feature of the large top heap (small top heap) that the top of the heap records the largest keyword (minimum keyword), making it easy to select the largest record (minimum record) from disorder every time Simple. Note: The big top heap constructs an increasing sequence, and the small top heap constructs a descending sequence.

(1) Construct the initial sequence of keywords to be sorted (R0, R1...Rn-1) into a large top heap, which is the initial unordered area;

(2) Exchange the top element R[0] with the last element R[n-1]. At this time, you will get a new disordered area (R0, R1....Rn-2) and a new ordered area. Sequential area (Rn-1), and satisfies R[0,1...n-2]<=R[n-1];

(3) Since the new heap top R[0] after the exchange may violate the properties of the heap, it is necessary to adjust the current unordered area (R0, R1...Rn-2) to the new heap, and then change R again [0] is exchanged with the last element of the disordered area to obtain a new disordered area (R0, R1...Rn-3) and a new ordered area (Rn-2, Rn-1). Repeat this process until The number of elements in the ordered area is n-1, and the entire sorting process is completed.

The operation process is as follows:

(1) Initialize the heap: construct [0...n-1] as a heap;

(2) Exchange the top element R[0] of the current unordered area with the last record of the interval, and then adjust the new unordered area to the new heap;

So for heap sorting, the two most important operations are to construct the initial heap and the adjustment heap. In fact, constructing the initial heap is also a process of adjusting the heap, but constructing the initial heap is to adjust all non-leaf nodes.

The example code is as follows:

//
//  main.c
//  Train
//
//  Created by chenyufeng on 16/1/30.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include <stdio.h>

void BuildHeap(int *a,int size);
void swap(int *a,int *b);
void HeapSort(int *a,int size);
void HeapAdjust(int *a,int i,int size);

int main(int argc,const char *argv[]){

    int a[] = {3,25,9,30,2};
    HeapSort(a, 5);
    for (int i = 0; i < 5; i++) {
        printf("%d ",a[i]);
    }

    return 0;
}

//建立堆
void BuildHeap(int *a,int size){

    for (int i = size - 1; i >= 0; i--) {
        HeapAdjust(a, i, size);
    }

}

//交换两个数
void swap(int *a,int *b){

    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//堆排序
void HeapSort(int *a,int size){

    BuildHeap(a, size);
    for (int i = size - 1; i >= 0; i--) {
        //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到后面；
        swap(&a[0], &a[i+1]);
        //重新调整堆为大顶堆；
        HeapAdjust(a, 0, i );
    }
}

//调整堆
void HeapAdjust(int *a,int i,int size){

    int lchild = 2 * i;//左孩子节点；
    int rchild = 2 * i + 1;//右孩子节点；
    int max = i;

    if (i <= size) {
        if (lchild <= size && a[lchild] > a[max]) {
            max = lchild;
        }

        if (rchild <= size && a[rchild] > a[max]) {
            max = rchild;
        }

        if (i != max) {
            swap(&a[i], &a[max]);
            //避免调整之后以max为父节点的子树不是堆；
            HeapAdjust(a, max, size);
        }
    }
}</stdio.h>

http://www.bkjia.com/PHPjc/1121830.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/1121830.htmlTechArticleClassic Algorithm Learning - Heap Sorting Heap sorting is a sorting that is slightly more troublesome than other sorting. It is a kind of sorting that uses heaps. Selection sorting by nature. The heap is actually a complete binary tree. As long as any...