前言
本博客是博主用于復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)以及算法的博客，如果疏忽出現(xiàn)錯(cuò)誤，還望各位指正。
堆排序（Heap Sort）概念
堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法，其核心思想是將待排序的序列構(gòu)建成一個(gè)最大堆（或最小堆），然后將堆頂元素與最后一個(gè)元素交換，再將剩余元素重新調(diào)整為最大堆（或最小堆），重復(fù)以上步驟直到所有元素都有序。
堆是一棵完全二叉樹，因此一般可以當(dāng)作數(shù)組處理。
對(duì)于最大堆，任何一個(gè)父節(jié)點(diǎn)的值都大于（或等于）其左右子節(jié)點(diǎn)的值；
對(duì)于最小堆，則是任何一個(gè)父節(jié)點(diǎn)的值都小于（或等于）其左右子節(jié)點(diǎn)的值。
建堆
上濾（插入新元素到堆中）
時(shí)間復(fù)雜度為O（N logN）
也就是一個(gè)一個(gè)插入，比如拿[46 23 26 24 10]來說，建堆過程就如下：
List<Integer> list = new ArrayList<>();
String[] num = in.nextLine().split(" ");
for(int i = 0;i<N;i++){
//小頂堆的形成，自上而下建堆，一個(gè)一個(gè)插入
if(list.size()==0){
list.add(Integer.parseInt(num[i]));
}else{
//如果長(zhǎng)度不是0，就插入后進(jìn)行比較
list.add(Integer.parseInt(num[i]));
int count = i;
while(count!=0){
int parent = 0;
if((count-1)%2==0){
parent = (count-1)/2;
}else if((count-2)%2==0){
parent =(count-2)/2;
}
if(list.get(count)<list.get(parent)){
int temp = list.get(count);
list.set(count,list.get(parent));
list.set(parent,temp);
count = parent;
}else{
break;
}
}
}
}下濾
一般用的是下濾，因?yàn)闀r(shí)間復(fù)雜度為O（N）
就是先整體插入，然后從倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)進(jìn)行堆調(diào)整：
1、找到倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)23，判斷其與子節(jié)點(diǎn)關(guān)系，發(fā)現(xiàn)比10大，于是互換
2、之后繼續(xù)尋找非葉子結(jié)點(diǎn)，找到46，46與10交換后，繼續(xù)與23交換
注意事項(xiàng)
建堆結(jié)束，兩種方法建立的堆可能不一樣，所以注意題目要求透露出的是哪一種。
比如要求上濾的：L2-012 關(guān)于堆的判斷 - 團(tuán)體程序設(shè)計(jì)天梯賽-練習(xí)集 (pintia.cn)
實(shí)現(xiàn)代碼：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] mn = in.nextLine().split(" ");
int N = Integer.parseInt(mn[0]);
int M = Integer.parseInt(mn[1]);
List<Integer> list = new ArrayList<>();
String[] num = in.nextLine().split(" ");
for(int i = 0;i<N;i++){
//小頂堆的形成
if(list.size()==0){
list.add(Integer.parseInt(num[i]));
}else{
//如果長(zhǎng)度不是0，就進(jìn)行比較
list.add(Integer.parseInt(num[i]));
int count = i;
while(count!=0){
int parent = 0;
if((count-1)%2==0){
parent = (count-1)/2;
}else if((count-2)%2==0){
parent =(count-2)/2;
}
if(list.get(count)<list.get(parent)){
int temp = list.get(count);
list.set(count,list.get(parent));
list.set(parent,temp);
count = parent;
}else{
break;
}
}
}
}
//System.out.println(list.toString());
//判斷
while(M-->0){
String[] judge = in.nextLine().split(" ");
//變成在數(shù)組中的下標(biāo)
int x = list.indexOf(Integer.parseInt(judge[0]));
if(judge[3].equals("root")){
if(x==0){
System.out.println("T");
}else{
System.out.println("F");
}
}else if(judge[3].equals("are")){
int y = list.indexOf(Integer.parseInt(judge[2]));
if((y-1)%2==0){
if(y+1==x){
System.out.println("T");
}else{
System.out.println("F");
}
}else if((y-2)%2==0){
if(y-1==x){
System.out.println("T");
}else{
System.out.println("F");
}
}
}else if(judge[3].equals("parent")){
int y = list.indexOf(Integer.parseInt(judge[5]));
if((y-1)%2==0){
if((y-1)/2==x){
System.out.println("T");
}else{
System.out.println("F");
}
}else if((y-2)%2==0){
if((y-2)/2==x){
System.out.println("T");
}else{
System.out.println("F");
}
}
}else if(judge[3].equals("child")){
int y = list.indexOf(Integer.parseInt(judge[5]));
if((2*y+1) == x || (2*y+2)== x){
System.out.println("T");
}else{
System.out.println("F");
}
}
}
}
}
當(dāng)然，更簡(jiǎn)單的，可以直接使用Java提供的類，直接使用優(yōu)先隊(duì)列toArray解決：
【PTA-訓(xùn)練day1】L2-012 關(guān)于堆的判斷 + L1-002打印沙漏_pta打印沙漏測(cè)試點(diǎn)-CSDN博客
Java優(yōu)先隊(duì)列
關(guān)于Java優(yōu)先隊(duì)列的一篇博主的博客詳細(xì)介紹
【Java】PriorityQueue--優(yōu)先級(jí)隊(duì)列_java priorityqueue-CSDN博客
隊(duì)列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu) ，但有些情況下， 操作的數(shù)據(jù)可能帶有優(yōu)先級(jí)，一般出隊(duì)列時(shí)，可能需要優(yōu)先級(jí)高的元素先出隊(duì)列 ，該中場(chǎng)景下，使用隊(duì)列顯然不合適，比如：在手機(jī)上玩游戲的時(shí)候，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話.
在這種情況下， 數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個(gè)最基本的操作，一個(gè)是返回最高優(yōu)先級(jí)對(duì)象，一個(gè)是添加新的對(duì)象。 這種數(shù)據(jù)結(jié)構(gòu)就是 優(yōu)先級(jí)隊(duì)列(Priority Queue)。
JDK1.8?中的?PriorityQueue底層使用了堆這種數(shù)據(jù)結(jié)構(gòu)?，而堆實(shí)際就是在完全二叉樹的基礎(chǔ)上進(jìn)行了一些調(diào)整。
默認(rèn)情況下是小根堆，如果需要大根堆，則需要構(gòu)建比較器。
其他方法與隊(duì)列無異。
PriorityQueue<Integer> q=new PriorityQueue<>(); //默認(rèn)小頂堆
PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->(b-a)); //大頂堆
q.contains(val);
Integer[] t=q.toArray(new Integer[n]); //將隊(duì)列轉(zhuǎn)化為數(shù)組堆排序
上述三種建堆的方法，每次之后將最頂點(diǎn)進(jìn)行一下處理（移除或者加入數(shù)組末尾等操作），然后重新建堆再操作即可實(shí)現(xiàn)堆排序。
應(yīng)用場(chǎng)景
堆排序使用場(chǎng)景堆排序的使用場(chǎng)景與其他排序算法類似，適用于需要對(duì)大量數(shù)據(jù)進(jìn)行排序的場(chǎng)景。比如取出第k大（?。┑臄?shù)，這時(shí)候可以用堆排序。
優(yōu)/缺點(diǎn)
優(yōu)點(diǎn)主要包括：
時(shí)間復(fù)雜度較低：堆排序的時(shí)間復(fù)雜度為 O(NlogN)，相對(duì)于其他排序算法，其排序速度較快。
不占用額外空間：堆排序是一種原地排序算法，不需要額外的空間來存儲(chǔ)排序結(jié)果。
適用于大數(shù)據(jù)量的排序：堆排序的時(shí)間復(fù)雜度不隨數(shù)據(jù)量的增加而變化，因此適用于大數(shù)據(jù)量的排序。
缺點(diǎn)主要包括：
不穩(wěn)定性：由于堆排序是通過交換元素來實(shí)現(xiàn)排序的，因此在排序過程中可能會(huì)破壞原有的相對(duì)順序，導(dǎo)致排序結(jié)果不穩(wěn)定。文章來源：http://www.zghlxwxcb.cn/news/detail-848771.html
實(shí)現(xiàn)復(fù)雜：相對(duì)于其他排序算法，堆排序的實(shí)現(xiàn)稍微復(fù)雜一些（不過借助Java提供的優(yōu)先隊(duì)列可以簡(jiǎn)單實(shí)現(xiàn)），需要理解堆數(shù)據(jù)結(jié)構(gòu)的基本原理和實(shí)現(xiàn)過程。文章來源地址http://www.zghlxwxcb.cn/news/detail-848771.html
代碼（后續(xù)寫了再上傳，咕咕咕）
到了這里，關(guān)于（Java）數(shù)據(jù)結(jié)構(gòu)——排序（第一節(jié)）堆排序+PTA L2-012 關(guān)于堆的判斷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
