? ? ? ? ? ? ? ? ? ? ? ? 普通隊列: ? 先進先出, 后進后出

priority queue(優先隊列): ? 出隊順序與入隊順序無關； 和優先級相關

?

二叉堆

葉子節點： ?一棵樹當中沒有子結點（即度為0）的結點稱為葉子節點，簡稱“葉子”

?

??從數組下標1開始存儲, 最后一個非葉子節點的索引: count/2

?

?從數組下標0開始存儲,最后一個非葉子節點的索引: (count-1)/2

?

? 數組實現二叉堆

public class MaxHeap {private int count;private int capacaity;private int[] data;public MaxHeap(int capacity){data = new int[capacity+1];this.capacaity = capacity;}public int size(){return count;}boolean isEmpty(){return count == 0 ;}public void insert(int item){if(count+1 > capacaity)return;// 從數組下標為1的位置開始插入元素data[count+1] = item;count++;shiftUp(count);}// 取出最大的值public int extractMax(){if(count < 1)return -1;int ret = data[1];data[1] = data[count]; // 將最后一個元素放在第一個元素的位置上count--;shiftDown(1);return ret;}private void shiftDown(int k){while(2*k <= count){int j = 2*k; // 在此輪循環中,data[k]和data[j]交換位置// 判斷是否有右孩子if(j+1<=count && data[j] < data[j+1]){j = j+1;}if(data[k] >= data[j]){break;}int temp = data[k];data[k] = data[j];data[j] = temp;k = j;}}private void shiftUp(int k){while(k > 1 && (data[k/2] < data[k])){int temp = data[k/2];data[k/2] = data[k];data[k] = temp;k = k/2; }}public void printMaxHeap(){for(int i=1; i<=count; i++){System.out.println("下標"+i+" ="+data[i]);}}public static void main(String[] args){MaxHeap maxHeap = new MaxHeap(100);for(int i=0; i<15; i++){maxHeap.insert(i);}System.out.println(maxHeap.size());maxHeap.printMaxHeap();System.out.println(maxHeap.extractMax());maxHeap.printMaxHeap();} }

?

?排序算法的穩定性

?

?

?索引堆

package com.heap;/// 索引最大堆 public class IndexMaxHeap {private int count; // 元素個數private int capacaity; // 元素容量private int[] data; // 存儲數據private int[] indexs; // 存儲數據的索引public IndexMaxHeap(int capacity){data = new int[capacity+1];indexs = new int[capacity+1];this.capacaity = capacity;}public int size(){return count;}boolean isEmpty(){return count == 0 ;}// 傳入的i對用戶而言,是從0索引開始的public void insert(int i, int item){if(count+1 > capacaity)return;if(i+1 < 1 || i+1 > capacaity)return;// 從數組下標為1的位置開始插入元素data[i+1] = item;indexs[count+1] = i+1;count++;shiftUp(count);}public int extractMax(){if(count < 1)return -1;int ret = data[indexs[1]];indexs[1] = indexs[count]; count--;shiftDown(1);return ret;}private void shiftDown(int k){while(2*k <= count){int j = 2*k; // 在此輪循環中,data[k]和data[j]交換位置// 判斷是否有右孩子if(j+1<=count && data[indexs[j]] < data[indexs[j+1]]){j = j+1;}if(data[indexs[k]] >= data[indexs[j]]){break;}int temp = indexs[k];indexs[k] = indexs[j];indexs[j] = temp;k = j;}}private void shiftUp(int k){while(k > 1 && (data[indexs[k/2]] < data[indexs[k]])){int temp = indexs[k/2];indexs[k/2] = indexs[k];indexs[k] = temp;k = k/2; }}public void printMaxHeap(){System.out.println("===");for(int i=1; i<=count; i++){System.out.println("下標"+i+" ="+data[i]);}}public void printMaxIndexHeap(){System.out.println("===");for(int i=1; i<=count; i++){System.out.println("下標"+i+" ="+data[indexs[i]]);}}public static void main(String[] args){IndexMaxHeap maxHeap = new IndexMaxHeap(100);for(int i=0; i<15; i++){maxHeap.insert(i, (int)(Math.random() * 100));}System.out.println(maxHeap.size());maxHeap.printMaxIndexHeap();maxHeap.printMaxHeap();int max = maxHeap.extractMax();System.out.println("max="+max);maxHeap.printMaxIndexHeap(); // System.out.println(maxHeap.extractMax()); // maxHeap.printMaxIndexHeap(); // // // int[] arr = {5,4,10,2,12,7,9}; // maxHeap.printMaxHeap();} }

?

總結

以上是生活随笔為你收集整理的数据结构:堆排序一（heap sort）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。