堆及堆排序

堆结构,优先级队列

大根堆（最大堆）是一种特殊的二叉树结构，它满足以下两个条件：

• 完全二叉树：大根堆是一棵完全二叉树，即除了最后一层外，每一层的节点都是满的，并且最后一层的节点从左到右依次排列。
• 堆序性质：大根堆中每个节点的值都大于或等于其子节点的值。换句话说，根节点是整个堆中的最大值。

调整代码

//新加入大根堆堆尾的数据向上调整
//从上往下构造大根堆
public static void heapInsert1(int[] arr, int i){
    while (arr[i] > arr[(i-1)/2]){
        swap(aar, i, (i_1)/2)
        i = (i-1)/2
    }
}

//从底往上构造大根堆，新的数往下对比
public static void heapInsert2(int[] arr, int i){
    while ((arr[i] < arr[i * 2 + 1] || arr[i] < arr[i * 2 + 2]&&(arr.length>i*2+1||arr.length>i*2+2))){
        int best = i;
        if (arr[i * 2 +1] < arr[i * 2 + 2]){
            best = i * 2 + 2;
        }
        else {
            best = i * 2 + 1;
        }
        swap(arr, i, best);
        i = best;
    }
}

//往下调整,大根堆中i位置数值变了
public static void heapify(int[] arr, int i, int size){
    int l = i * 2 +1;
    while (l < size){
        int best;
        if(l + 1 < size && arr[l + 1] > arr[l]){
            best = l + 1;
        }
        else{
            best = l;
        }
        if (arr[best] < arr[i]){
            break;
        }
        swap(arr, best, i);
        i = best;
        l = i * 2 +1;
    }
}

堆排序

public static void heapSort1(int[] arr){
    int n = arr.length;
    // 从上往下构造大根堆
    //log1+log2+...+logn 收敛于O(n*logn)
    for (int i = 0;i < n;i++){
        heapInsert1(arr, i);
    }
    // 从下往上构造大根堆
    // for (int i = n-1; i >= 0; i--){
    //     heapInsert2(arr, i);
    // }
    int size = n;
    //调整过程O(n*logn)
    while (size > 1){
        swap(arr, 0, --size);
        heapify(arr, 0 ,size);
    }
}

cpp实现

#include <iostream>
using namespace std;

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

// 新加入大根堆堆尾的数据向上调整
void heapInsert1(int arr[], int i)
{
    while (arr[i] > arr[(i - 1) / 2])
    {
        swap(arr[i], arr[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// 从底往上构造大根堆，新入堆的值向下对比
void heapInsert2(int arr[], int i, int n)
{
    while ((arr[i] < arr[i * 2 + 1] || arr[i] < arr[i * 2 + 2]) && (i * 2 + 1 < n && i * 2 + 2 < n))
    {
        int best = i;
        if (arr[i * 2 + 2] < arr[i * 2 + 1])
        {
            best = i * 2 + 1;
        }
        else
        {
            best = i * 2 + 2;
        }
        swap(arr[i], arr[best]);
        i = best;
    }
}

// 向下调整，大根堆中i位置数值变了
void heapify(int arr[], int n, int i)
{
    int largest = i;       // 初始化 largest 为根节点
    int left = 2 * i + 1;  // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于 largest
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果 largest 不是根节点
    if (largest != i)
    {
        swap(arr[i], arr[largest]);

        // 递归地对受影响的子树进行 heapify
        heapify(arr, n, largest);
    }
}

void heapsort1(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        heapInsert1(arr, i);
    }
    int size = n;
    while (size > 1)
    {
        swap(arr[0], arr[--size]);
        heapify(arr, size, 0);
    }
}

void heapsort2(int arr[], int n)
{
    for (int i = n - 1; i >= 0; i--)
    {
        heapInsert2(arr, i, n);
    }
    int size = n;
    while (size > 1)
    {
        swap(arr[0], arr[--size]);
        heapify(arr, size, 0);
    }
}

int main()
{
    int n;
    cin >> n;
    int arr1[n], arr2[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr1[i];
        arr2[i] = arr1[i];
    }
    heapsort1(arr1, n);
    for (int i = 0; i < n; i++)
    {
        cout << arr1[i] << " ";
    }
    cout << endl;
    heapsort2(arr2, n);
    for (int i = 0; i < n; i++)
    {
        cout << arr2[i] << " ";
    }
}

比较器定制

public static class Employee{
    public int company;
    public int age;
    public Employee(int c, int a){
        company = c;
        age = a;
    }
}

public static EmployeeComparator implements Comparator<Employee>{
    @Override
    public int compare(Employee 01, Employee o2){
        //返回正数o1优先级高，返回负数o2优先级高，优先级一致返回0
        return o1.age - o2.age;
    }
}

Employee []arr={};
Array.sort(arr,new EmployeeComparator());
Array.sort(arr,(a,b)->b.age-a.age);