JAVA算法起步之堆排序?qū)嵗?/h1>
更新時(shí)間：2014年02月10日 15:17:15 作者：
這篇文章主要介紹了JAVA算法起步之堆排序?qū)嵗?需要的朋友可以參考下
學(xué)習(xí)堆排序，首先需要明白堆的概念，堆是一個(gè)數(shù)組?？梢越飘?dāng)做完全二叉樹的數(shù)組存儲(chǔ)方式。但是跟他還有其他的性質(zhì)，就是類似于二叉排序樹。有最大堆跟最小堆之分，最大堆是指根節(jié)點(diǎn)的值都大于子節(jié)點(diǎn)的值，而最小堆的是根節(jié)點(diǎn)的值小于其子節(jié)點(diǎn)的值。堆排序一般用的是最大堆，而最小堆可以構(gòu)造優(yōu)先隊(duì)列。堆里面有一個(gè)方法是用來(lái)維護(hù)堆的性質(zhì)，也就是我們下面代碼中的maxheap方法，這是維護(hù)最大堆性質(zhì)的方法，第一個(gè)參數(shù)就是堆也就是數(shù)組，第二個(gè)參數(shù)是調(diào)整堆的具體節(jié)點(diǎn)位置，可能這個(gè)節(jié)點(diǎn)的值不符合最大堆的性質(zhì)，那么這個(gè)值得位置就作為參數(shù)，而size其實(shí)是堆內(nèi)實(shí)際存儲(chǔ)的有效元素個(gè)數(shù)?？赡軘?shù)組的長(zhǎng)度就是堆內(nèi)實(shí)際存儲(chǔ)的元素個(gè)數(shù)，但是不一定所有的數(shù)據(jù)我們都需要進(jìn)行構(gòu)建最大堆。算法導(dǎo)論中說(shuō)的得到左子結(jié)點(diǎn)是2xi但是我們數(shù)組是從0開始計(jì)數(shù)的，所以左子結(jié)點(diǎn)就成了2xi+1，buildheap就是構(gòu)建一個(gè)最大堆，我們?nèi)?分之長(zhǎng)度的原因是，這些點(diǎn)的子節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，所以我們通過(guò)從下向上進(jìn)行排序來(lái)構(gòu)建一個(gè)最大堆。保證了我們堆內(nèi)所有節(jié)點(diǎn)都滿足最大堆性質(zhì)。最后堆排序就是把第一個(gè)節(jié)點(diǎn)取出來(lái)，將剩下的節(jié)點(diǎn)再進(jìn)行堆排序，再取出根節(jié)點(diǎn)。這樣保證我們每次取出都是最大值。
復(fù)制代碼 代碼如下:
public class HeapSort {
private int getLeft(int i){
return 2*i+1;
}
private int getRight(int i){
return 2*i+2;
}
public void maxheap(int[] heap,int loc,int size){
int l=getLeft(loc);
int r=getRight(loc);
int largest=loc;
if(l<size&&heap[l]>heap[loc]){
largest=l;
}
if (r<size&&heap[r]>heap[largest]) {
largest=r;
}
if(largest!=loc){
int cache=heap[loc];
heap[loc]=heap[largest];
heap[largest]=cache;
maxheap(heap, largest, size);
}
}
public void buildheap(int[] heap){
for(int i=heap.length/2;i>=0;i--){
maxheap(heap, i, heap.length);
}
}
public void sort(int[] heap){
buildheap(heap);
for(int i=heap.length-1;i>1;i--){
int cache=heap[0];
heap[0]=heap[i];
heap[i]=cache;
maxheap(heap, 0,i );
}
int cache=heap[0];
heap[0]=heap[1];
heap[1]=cache;
}
public static void main(String[] args) {
int[] heap=new int[]{4,1,5,3,7,12,65,7};
HeapSort hs=new HeapSort();
hs.sort(heap);
for (int i = 0; i < heap.length; i++) {
System.out.println(heap[i]);
}
}
}
您可能感興趣的文章:- Java算法之?dāng)?shù)組冒泡排序代碼實(shí)例講解
- Java算法之串的簡(jiǎn)單處理
- Java算法實(shí)現(xiàn)調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)之前的講解
- Java算法實(shí)現(xiàn)楊輝三角的講解
- Java算法之冒泡排序?qū)嵗a
- Java算法之最長(zhǎng)公共子序列問(wèn)題(LCS)實(shí)例分析
- java算法實(shí)現(xiàn)紅黑樹完整代碼示例
- Java算法之堆排序代碼示例
- java算法之二分查找法的實(shí)例詳解
- java算法導(dǎo)論之FloydWarshall算法實(shí)現(xiàn)代碼
- java算法實(shí)現(xiàn)預(yù)測(cè)雙色球中獎(jiǎng)號(hào)碼
- Java算法之遞歸算法計(jì)算階乘
- JAVA算法起步之插入排序?qū)嵗?/a>
- JAVA算法起步之快速排序?qū)嵗?/a>
- 關(guān)于各種排列組合java算法實(shí)現(xiàn)方法
- Java算法之時(shí)間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算
相關(guān)文章
-
springboot實(shí)現(xiàn)定時(shí)器(一看即會(huì),非常簡(jiǎn)單)
這篇文章主要介紹了springboot實(shí)現(xiàn)定時(shí)器(一看即會(huì),非常簡(jiǎn)單),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教 2023-12-12
-
SpringBoot處理JSON數(shù)據(jù)方法詳解
這篇文章主要介紹了SpringBoot整合Web開發(fā)中Json數(shù)據(jù)處理，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧 2022-10-10
-
JAVA中關(guān)于Long類型返回前端精度丟失問(wèn)題處理辦法
這篇文章主要介紹了后端JavaBean的id屬性從Long類型改為雪花算法后出現(xiàn)的精度丟失問(wèn)題,解決方案包括將id字段類型改為字符串或使用Jackson序列化方式,需要的朋友可以參考下 2024-11-11
-
java實(shí)現(xiàn)人工智能化屏幕監(jiān)控窗口
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)人工智能化屏幕監(jiān)控窗口，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2018-09-09
-
Java讀寫鎖ReadWriteLock的創(chuàng)建使用及測(cè)試分析示例詳解
這篇文章主要為大家介紹了Java讀寫鎖ReadWriteLock的創(chuàng)建使用及測(cè)試分析示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪 2023-01-01
-
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)人機(jī)猜拳游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下 2020-07-07
-
mybatis寫xml時(shí)數(shù)字類型千萬(wàn)別用 !=‘‘(不為空串)進(jìn)行判斷的示例詳解
這篇文章主要介紹了mybatis寫xml時(shí)數(shù)字類型千萬(wàn)別用 !=‘‘(不為空串)進(jìn)行判斷的示例詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下 2020-09-09
-
發(fā)現(xiàn)有很多小伙伴都不會(huì)用IDEA打jar包,今天給大家詳細(xì)總結(jié)了兩種IDEA打jar包的方式,對(duì)正在學(xué)習(xí)IDEA使用的小伙伴很有幫助,需要的朋友可以參考下 2021-05-05
-
Java Web監(jiān)聽器如何實(shí)現(xiàn)定時(shí)發(fā)送郵件
這篇文章主要介紹了Java Web監(jiān)聽器如何實(shí)現(xiàn)定時(shí)發(fā)送郵件,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下 2020-12-12
-
java使用FastJson解析Json數(shù)據(jù)
本篇文章主要介紹了java使用FastJson解析Json數(shù)據(jù)，fastjson 是一個(gè)性能極好的用 Java 語(yǔ)言實(shí)現(xiàn)的 JSON 解析器和生成器，有興趣的可以了解一下。
2017-02-02
最新評(píng)論
學(xué)習(xí)堆排序，首先需要明白堆的概念，堆是一個(gè)數(shù)組?？梢越飘?dāng)做完全二叉樹的數(shù)組存儲(chǔ)方式。但是跟他還有其他的性質(zhì)，就是類似于二叉排序樹。有最大堆跟最小堆之分，最大堆是指根節(jié)點(diǎn)的值都大于子節(jié)點(diǎn)的值，而最小堆的是根節(jié)點(diǎn)的值小于其子節(jié)點(diǎn)的值。堆排序一般用的是最大堆，而最小堆可以構(gòu)造優(yōu)先隊(duì)列。堆里面有一個(gè)方法是用來(lái)維護(hù)堆的性質(zhì)，也就是我們下面代碼中的maxheap方法，這是維護(hù)最大堆性質(zhì)的方法，第一個(gè)參數(shù)就是堆也就是數(shù)組，第二個(gè)參數(shù)是調(diào)整堆的具體節(jié)點(diǎn)位置，可能這個(gè)節(jié)點(diǎn)的值不符合最大堆的性質(zhì)，那么這個(gè)值得位置就作為參數(shù)，而size其實(shí)是堆內(nèi)實(shí)際存儲(chǔ)的有效元素個(gè)數(shù)?？赡軘?shù)組的長(zhǎng)度就是堆內(nèi)實(shí)際存儲(chǔ)的元素個(gè)數(shù)，但是不一定所有的數(shù)據(jù)我們都需要進(jìn)行構(gòu)建最大堆。算法導(dǎo)論中說(shuō)的得到左子結(jié)點(diǎn)是2xi但是我們數(shù)組是從0開始計(jì)數(shù)的，所以左子結(jié)點(diǎn)就成了2xi+1，buildheap就是構(gòu)建一個(gè)最大堆，我們?nèi)?分之長(zhǎng)度的原因是，這些點(diǎn)的子節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，所以我們通過(guò)從下向上進(jìn)行排序來(lái)構(gòu)建一個(gè)最大堆。保證了我們堆內(nèi)所有節(jié)點(diǎn)都滿足最大堆性質(zhì)。最后堆排序就是把第一個(gè)節(jié)點(diǎn)取出來(lái)，將剩下的節(jié)點(diǎn)再進(jìn)行堆排序，再取出根節(jié)點(diǎn)。這樣保證我們每次取出都是最大值。
public class HeapSort {
private int getLeft(int i){
return 2*i+1;
}
private int getRight(int i){
return 2*i+2;
}
public void maxheap(int[] heap,int loc,int size){
int l=getLeft(loc);
int r=getRight(loc);
int largest=loc;
if(l<size&&heap[l]>heap[loc]){
largest=l;
}
if (r<size&&heap[r]>heap[largest]) {
largest=r;
}
if(largest!=loc){
int cache=heap[loc];
heap[loc]=heap[largest];
heap[largest]=cache;
maxheap(heap, largest, size);
}
}
public void buildheap(int[] heap){
for(int i=heap.length/2;i>=0;i--){
maxheap(heap, i, heap.length);
}
}
public void sort(int[] heap){
buildheap(heap);
for(int i=heap.length-1;i>1;i--){
int cache=heap[0];
heap[0]=heap[i];
heap[i]=cache;
maxheap(heap, 0,i );
}
int cache=heap[0];
heap[0]=heap[1];
heap[1]=cache;
}
public static void main(String[] args) {
int[] heap=new int[]{4,1,5,3,7,12,65,7};
HeapSort hs=new HeapSort();
hs.sort(heap);
for (int i = 0; i < heap.length; i++) {
System.out.println(heap[i]);
}
}
}
- Java算法之?dāng)?shù)組冒泡排序代碼實(shí)例講解
- Java算法之串的簡(jiǎn)單處理
- Java算法實(shí)現(xiàn)調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)之前的講解
- Java算法實(shí)現(xiàn)楊輝三角的講解
- Java算法之冒泡排序?qū)嵗a
- Java算法之最長(zhǎng)公共子序列問(wèn)題(LCS)實(shí)例分析
- java算法實(shí)現(xiàn)紅黑樹完整代碼示例
- Java算法之堆排序代碼示例
- java算法之二分查找法的實(shí)例詳解
- java算法導(dǎo)論之FloydWarshall算法實(shí)現(xiàn)代碼
- java算法實(shí)現(xiàn)預(yù)測(cè)雙色球中獎(jiǎng)號(hào)碼
- Java算法之遞歸算法計(jì)算階乘
- JAVA算法起步之插入排序?qū)嵗?/a>
- JAVA算法起步之快速排序?qū)嵗?/a>
- 關(guān)于各種排列組合java算法實(shí)現(xiàn)方法
- Java算法之時(shí)間復(fù)雜度和空間復(fù)雜度的概念和計(jì)算
相關(guān)文章
-
springboot實(shí)現(xiàn)定時(shí)器(一看即會(huì),非常簡(jiǎn)單)
這篇文章主要介紹了springboot實(shí)現(xiàn)定時(shí)器(一看即會(huì),非常簡(jiǎn)單),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12 -
SpringBoot處理JSON數(shù)據(jù)方法詳解
這篇文章主要介紹了SpringBoot整合Web開發(fā)中Json數(shù)據(jù)處理，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-10-10 -
JAVA中關(guān)于Long類型返回前端精度丟失問(wèn)題處理辦法
這篇文章主要介紹了后端JavaBean的id屬性從Long類型改為雪花算法后出現(xiàn)的精度丟失問(wèn)題,解決方案包括將id字段類型改為字符串或使用Jackson序列化方式,需要的朋友可以參考下2024-11-11 -
java實(shí)現(xiàn)人工智能化屏幕監(jiān)控窗口
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)人工智能化屏幕監(jiān)控窗口，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-09-09 -
Java讀寫鎖ReadWriteLock的創(chuàng)建使用及測(cè)試分析示例詳解
這篇文章主要為大家介紹了Java讀寫鎖ReadWriteLock的創(chuàng)建使用及測(cè)試分析示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-01-01 - 這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)人機(jī)猜拳游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
-
mybatis寫xml時(shí)數(shù)字類型千萬(wàn)別用 !=‘‘(不為空串)進(jìn)行判斷的示例詳解
這篇文章主要介紹了mybatis寫xml時(shí)數(shù)字類型千萬(wàn)別用 !=‘‘(不為空串)進(jìn)行判斷的示例詳解,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-09-09 - 發(fā)現(xiàn)有很多小伙伴都不會(huì)用IDEA打jar包,今天給大家詳細(xì)總結(jié)了兩種IDEA打jar包的方式,對(duì)正在學(xué)習(xí)IDEA使用的小伙伴很有幫助,需要的朋友可以參考下2021-05-05
-
Java Web監(jiān)聽器如何實(shí)現(xiàn)定時(shí)發(fā)送郵件
這篇文章主要介紹了Java Web監(jiān)聽器如何實(shí)現(xiàn)定時(shí)發(fā)送郵件,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-12-12 -
java使用FastJson解析Json數(shù)據(jù)
本篇文章主要介紹了java使用FastJson解析Json數(shù)據(jù)，fastjson 是一個(gè)性能極好的用 Java 語(yǔ)言實(shí)現(xiàn)的 JSON 解析器和生成器，有興趣的可以了解一下。2017-02-02