Classificação da pilha: usando grandes pilhas de raiz
Todas as matrizes são inseridas na pilha, então a pilha é liberada da pilha e inserida de volta na matriz de trás para a frente, e a matriz é encomendada de pequena a grande.
Classe pública maxheap <t estende comparável <?? super t >> {private t [] dados; Tamanho privado int; Capacidade privada int; public MaxHeap (int capacidade) {this.data = (t []) novo comparável [capacidade + 1]; tamanho = 0; this.Capacity = Capacidade; } public int size () {return this.size; } public boolean isEmpty () {return size == 0; } public int getCapacity () {return this.Capacity; } / ** * @return Visualize a raiz máxima (veja apenas sem exclusão, em comparação com POPMAX) * / public T SeekMax () {retornar dados [1]; } public void swap (int i, int j) {if (i! = j) {t temp = dados [i]; dados [i] = dados [j]; dados [j] = temp; }} public void insert (item t) {size ++; dados [tamanho] = item; shiftUp (tamanho); } / ** * @return pop a raiz máxima (pop-up significa exclusão, comparada com seekmax) * / public t POPMAX () {swap (1, tamanho--); ShiftDown (1); retornar dados [tamanho + 1]; } / ** * @param criança A marca do canto inferior do nó infantil é criança, e a tabela de canto inferior do nó pai é filho / 2 * / public void ShiftUp (int filho) {while (Child> 1 && Data [Child] .compareto (Data [Child / 2])> 0) {Swap (criança, criança, / 2); criança = criança / 2; } } /** * @param a lower corner mark of an element in the data array* @param b The lower corner mark of an element in the data array* @return The lower corner mark of which element is large*/ private int max(int a, int b) { if (data[a].compareTo(data[b]) < 0) {//If data[b] big return b;//Return b } else {//If data[a] big Retorne a; // retorna a}}/*** @param Uma marca de canto inferior de um elemento na matriz de dados* @param b Marca do canto inferior de um elemento na matriz de dados* @param c marca de canto inferior de um elemento na matriz de dados* @Return a marca de canto inferior de um elemento na matriz de dados*/private int (int a, int b, int b) { maior = max (maior, c); retornar maior; }/** * @param Pai A marca do canto inferior do nó pai é pai, e as mesas de canto inferior da esquerda e direita dois nós filhos são: pai * 2 e pai * 2 + 1 */public void shiftDown (int father) {while) {int lchild = pai * 2; // filho esquerdo int rchild = pad * 2 + 1; //; Quem é a marca do canto inferior dos pais, nós à esquerda e direita? If (lchild> size) {// se o nó do pai não deixou o filho nem o filho direito retornar; } else if (rchild> size) {// Se o nó do pai só deixou o filho, nenhum filho do filho direito = max (pai, lchild); } else {// Se o nó do pai deixou o filho e o novo filho da criança = max (pai, lchild, rchild); } if (newfather == pai) {// significa que o pai é maior que ambos os nós filhos, e o nome da tabela já é uma grande pilha de raiz, portanto não há necessidade de continuar ajustando o retorno; } else {// Caso contrário, você precisa continuar ajustando a pilha até que a condição da grande raíze seja atendida (pai, novato); // troca de valor pai = novato; // Atualize o valor do pai, o que é equivalente a continuar a ajustar o shiftDown (novato)}}}} estática pública <t undends comparável <?? Super T >> Void Sort (t [] arr) {int len = arr.length; // in-heap maxheap <t> maxheap = novo maxheap <T> (len); for (int i = 0; i <len; i ++) {maxheap.insert (arr [i]); } // out-heap para (int i = len-1; i> = 0; i-) {arr [i] = maxheap.popmax (); }} public static void printarr (objeto [] arr) {for (objeto o: arr) {System.out.print (O); System.out.print ("/t"); } System.out.println (); } public static void main (string args []) {integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; Priprearr (arr); // 3 5 1 7 2 9 8 0 4 6 Classificar (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Classificação da pilha: construa a pilha na matriz (heap máximo)
Classe pública maxheap <t estende comparável <?? super t >> {private t [] dados; Tamanho privado int; Capacidade privada int; public MaxHeap (int Capacidade) {this.Capacity = Capacidade; this.size = 0; this.data = (t []) nova comparável [capacidade + 1]; } public maxheap (t [] arr) {// heapify, prisioneira de capacidade de heap = arr.length; dados = (t []) nova comparável [capacidade + 1]; System.arraycopy (arr, 0, dados, 1, ar.Length); tamanho = arr.length; for (int i = size / 2; i> = 1; i--) {shiftDown (i); }} public int size () {return this.size; } public int getCapacity () {return this.Capacity; } public boolean isEmpty () {return size == 0; } public t reequeMmax () {retorna dados [1]; } public void swap (int i, int j) {if (i! = j) {t temp = dados [i]; dados [i] = dados [j]; dados [j] = temp; }} public void insert (item t) {size ++; dados [tamanho] = item; shiftUp (tamanho); } public T POPMAX () {SWAP (1, tamanho--); ShiftDown (1); retornar dados [tamanho + 1]; } public void shiftUp (int filho) {while (filho> 1 && data [filho] .compareto (dados [filho / 2])> 0) {swap (criança, criança / 2); criança /= 2; }}/*** @param Uma marca de canto inferior de um elemento na matriz de dados* @param b Marca do canto inferior de um elemento na matriz de dados* @return retorna qual elemento é maior, a marca do canto inferior do qual o elemento é maior*/private int max (int a, int b) {if (Data] .compareto (Data/[b]) <0) {Int] {int b) {if (a]. Dados [a] Big Return a; // retorna a}}/*** @param Uma marca de canto inferior de um elemento na matriz de dados* @param b Marca do canto inferior de um elemento na matriz de dados* @param c A marca do canto inferior de um elemento de um elemento b); maior = max (maior, c); retornar maior; } public void shiftDown (int pai) {while (true) {int lchild = pai * 2; int rchild = pai * 2 + 1; int newfather = pai; // Não importa se a tarefa é atribuída aqui. Se o retorno a seguir for alterado para quebrar, ele deverá ser atribuído se (lchild> size) {// se não houver filhos à esquerda e direita retornar; } else if (rchild> size) {// Se não houver um novo filho da criança = max (pai, lchild); } else {// se houver um novato para crianças esquerda e direita = max (pai, lchild, rchild); } if (newfather == pai) {// Se o nó pai original for o maior de três, você não precisará continuar a resolver o retorno da pilha; } else {// O nó pai não é o maior, troque as crianças mais velhas e continue a ajustar os para baixo até que a pilha de raiz grande seja satisfeita (newfather, pai); Pai = Newfather; // equivalente ao shiftDown (novato). Se o novato acaba sendo o filho esquerdo do pai, é equivalente a shiftdown (2*pai)}}} public static <t estende comparável <?? Super T >> Void Sort (t [] arr) {int len = arr.length; Maxheap <t> maxheap = new maxheap <> (arr); for (int i = len-1; i> = 0; i--) {arr [i] = maxheap.popmax (); }} public static void printarr (objeto [] arr) {for (objeto o: arr) {System.out.print (O); System.out.print ("/t"); } System.out.println (); } public static void main (string args []) {integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; Priprearr (arr); // 3 5 1 7 2 9 8 0 4 6 Classificar (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}O exemplo de classificação de heap acima (implementação da matriz Java) é todo o conteúdo que compartilho com você. Espero que você possa lhe dar uma referência e espero que você possa apoiar mais o wulin.com.