{"id":4775,"date":"2023-05-25T09:52:59","date_gmt":"2023-05-25T12:52:59","guid":{"rendered":"https:\/\/elemarjr.com\/clube-de-estudos\/?p=4775"},"modified":"2023-10-21T21:37:14","modified_gmt":"2023-10-22T00:37:14","slug":"binary-heap-e-heapsort-o-que-sao-e-como-funcionam","status":"publish","type":"artigos","link":"https:\/\/elemarjr.com\/clube-de-estudos\/artigos\/binary-heap-e-heapsort-o-que-sao-e-como-funcionam\/","title":{"rendered":"Binary Heap e HeapSort – O que s\u00e3o e como funcionam"},"content":{"rendered":"\n

O que \u00e9 Binary Heap<\/em>?<\/h2>\n\n\n\n

Defini\u00e7\u00e3o de Binary Heap<\/em><\/h3>\n\n\n\n

Um Binary Heap<\/em> \u00e9 uma estrutura de dados que representa uma \u00e1rvore bin\u00e1ria completa. Nesse tipo de \u00e1rvore, todos os n\u00edveis, exceto possivelmente o \u00faltimo, est\u00e3o completamente preenchidos, e todos os n\u00f3s est\u00e3o t\u00e3o \u00e0 esquerda quanto poss\u00edvel.<\/p>\n\n\n\n

Max Heap<\/em> e Min Heap<\/em><\/h3>\n\n\n\n

Existem duas varia\u00e7\u00f5es de Binary Heap<\/em>: Max Heap <\/em>e Min Heap<\/em>. No Max Heap<\/em>, os pais t\u00eam valores maiores que ou iguais aos dos filhos, enquanto no Min Heap<\/em>, os pais t\u00eam valores menores que ou iguais aos dos filhos.<\/p>\n\n\n\n

Como funciona um Binary Heap<\/em><\/h2>\n\n\n\n

Propriedade de Heap<\/em><\/h3>\n\n\n\n

A principal caracter\u00edstica que define um Binary Heap <\/em>\u00e9 a propriedade de heap<\/em>. Cada n\u00f3 da \u00e1rvore deve respeitar essa propriedade em rela\u00e7\u00e3o aos seus filhos, garantindo a ordena\u00e7\u00e3o dos elementos.<\/p>\n\n\n\n

Opera\u00e7\u00f5es em Binary Heap<\/em><\/h3>\n\n\n\n

As opera\u00e7\u00f5es comuns em um Binary Heap <\/em>incluem inser\u00e7\u00e3o, exclus\u00e3o e busca. Essas opera\u00e7\u00f5es garantem a manuten\u00e7\u00e3o da propriedade de heap<\/em>.<\/p>\n\n\n\n

O que \u00e9 HeapSort<\/em>?<\/h2>\n\n\n\n

Descri\u00e7\u00e3o do algoritmo HeapSort<\/em><\/h3>\n\n\n\n

HeapSort<\/em> \u00e9 um algoritmo de ordena\u00e7\u00e3o que usa um Binary Heap <\/em>para classificar os elementos. Ele opera construindo o heap<\/em>, extraindo repetidamente o elemento m\u00e1ximo (ou m\u00ednimo) e reconstituindo o heap<\/em>.<\/p>\n\n\n\n

Como o HeapSort<\/em> funciona<\/h2>\n\n\n\n

Construindo o Heap<\/em><\/h3>\n\n\n\n

A primeira fase do HeapSort <\/em>envolve a constru\u00e7\u00e3o do heap <\/em>a partir do conjunto de dados. Esta etapa prepara a estrutura para a extra\u00e7\u00e3o dos elementos<\/p>\n\n\n\n

Extraindo o Elemento M\u00e1ximo ou M\u00ednimo<\/h3>\n\n\n\n

Depois que o heap<\/em> \u00e9 constru\u00eddo, o HeapSort <\/em>extrai repetidamente o elemento m\u00e1ximo (ou m\u00ednimo) da estrutura.<\/p>\n\n\n\n

Reconstitui\u00e7\u00e3o do Heap<\/em><\/h3>\n\n\n\n

Ap\u00f3s a extra\u00e7\u00e3o de um elemento, o HeapSort <\/em>reconstitui o heap <\/em>para manter a propriedade de heap<\/em>. Este passo \u00e9 repetido at\u00e9 que todos os elementos sejam extra\u00eddos e ordenados.<\/p>\n\n\n\n

A efici\u00eancia do HeapSort<\/em><\/h2>\n\n\n\n

Complexidade de tempo do HeapSort<\/em><\/h3>\n\n\n\n

A beleza do HeapSort <\/em>reside em sua efici\u00eancia. A complexidade de tempo do HeapSort <\/em>\u00e9 O(n log n)<\/em>, tornando-o eficiente para a ordena\u00e7\u00e3o de grandes conjuntos de dados.<\/p>\n\n\n\n

Binary Heap<\/em> e HeapSort<\/em> na pr\u00e1tica<\/h2>\n\n\n\n

Aplica\u00e7\u00f5es de Binary Heap <\/em>e HeapSort<\/em><\/h3>\n\n\n\n

Os conceitos de Binary Heap<\/em> e HeapSort<\/em> n\u00e3o s\u00e3o apenas teoria. Eles s\u00e3o aplicados em muitas \u00e1reas, como sistemas de banco de dados, simula\u00e7\u00e3o de eventos discretos e algoritmos de caminho mais curto.<\/p>\n\n\n\n

Exemplo de implementa\u00e7\u00e3o em C#<\/h3>\n\n\n\n
C#<\/span><\/path><\/path><\/svg><\/span>
using<\/span> System<\/span>;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>BinaryHeap<\/span><\/span>\n{<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[]<\/span> heap<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> size<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>BinaryHeap<\/span>(<\/span>int<\/span> capacity<\/span>)<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>heap<\/span> <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>capacity<\/span>]<\/span>;<\/span><\/span>\n        <\/span>size<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>void<\/span> <\/span>Heapify<\/span>(<\/span>int<\/span> index<\/span>)<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>int<\/span> largest <\/span>=<\/span> <\/span>index<\/span>;<\/span><\/span>\n        <\/span>int<\/span> leftChild <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> <\/span>index<\/span> <\/span>+<\/span> <\/span>1<\/span>;<\/span><\/span>\n        <\/span>int<\/span> rightChild <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> <\/span>index<\/span> <\/span>+<\/span> <\/span>2<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> <\/span>(<\/span>leftChild<\/span> <\/span><<\/span> <\/span>size<\/span> <\/span>&&<\/span> <\/span>heap<\/span>[<\/span>leftChild<\/span>]<\/span> <\/span>><\/span> <\/span>heap<\/span>[<\/span>largest<\/span>])<\/span><\/span>\n            <\/span>largest<\/span> <\/span>=<\/span> <\/span>leftChild<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> <\/span>(<\/span>rightChild<\/span> <\/span><<\/span> <\/span>size<\/span> <\/span>&&<\/span> <\/span>heap<\/span>[<\/span>rightChild<\/span>]<\/span> <\/span>><\/span> <\/span>heap<\/span>[<\/span>largest<\/span>])<\/span><\/span>\n            <\/span>largest<\/span> <\/span>=<\/span> <\/span>rightChild<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> <\/span>(<\/span>largest<\/span> <\/span>!=<\/span> <\/span>index<\/span>)<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>Swap<\/span>(<\/span>index<\/span>,<\/span> <\/span>largest<\/span>)<\/span>;<\/span><\/span>\n            <\/span>Heapify<\/span>(<\/span>largest<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>void<\/span> <\/span>Swap<\/span>(<\/span>int<\/span> i<\/span>,<\/span> <\/span>int<\/span> j<\/span>)<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>int<\/span> temp <\/span>=<\/span> <\/span>heap<\/span>[<\/span>i<\/span>]<\/span>;<\/span><\/span>\n        <\/span>heap<\/span>[<\/span>i<\/span>]<\/span> <\/span>=<\/span> <\/span>heap<\/span>[<\/span>j<\/span>]<\/span>;<\/span><\/span>\n        <\/span>heap<\/span>[<\/span>j<\/span>]<\/span> <\/span>=<\/span> <\/span>temp<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>Insert<\/span>(<\/span>int<\/span> value<\/span>)<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>if<\/span> <\/span>(<\/span>size<\/span> <\/span>==<\/span> <\/span>heap<\/span>.<\/span>Length<\/span>)<\/span><\/span>\n            <\/span>throw<\/span> <\/span>new<\/span> InvalidOperationException<\/span>(<\/span>"<\/span>Heap is full.<\/span>"<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>int<\/span> currentIndex <\/span>=<\/span> <\/span>size<\/span>;<\/span><\/span>\n        <\/span>heap<\/span>[<\/span>currentIndex<\/span>]<\/span> <\/span>=<\/span> <\/span>value<\/span>;<\/span><\/span>\n        <\/span>size<\/span>++;<\/span><\/span>\n<\/span>\n        <\/span>while<\/span> <\/span>(<\/span>currentIndex<\/span> <\/span>><\/span> <\/span>0<\/span> <\/span>&&<\/span> <\/span>heap<\/span>[<\/span>currentIndex<\/span>]<\/span> <\/span>><\/span> <\/span>heap<\/span>[(<\/span>currentIndex<\/span> <\/span>-<\/span> <\/span>1<\/span>)<\/span> <\/span>\/<\/span> <\/span>2<\/span>])<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>Swap<\/span>(<\/span>currentIndex<\/span>,<\/span> <\/span>(<\/span>currentIndex<\/span> <\/span>-<\/span> <\/span>1<\/span>)<\/span> <\/span>\/<\/span> <\/span>2<\/span>)<\/span>;<\/span><\/span>\n            <\/span>currentIndex<\/span> <\/span>=<\/span> <\/span>(<\/span>currentIndex<\/span> <\/span>-<\/span> <\/span>1<\/span>)<\/span> <\/span>\/<\/span> <\/span>2<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>int<\/span> <\/span>RemoveMax<\/span>()<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>if<\/span> <\/span>(<\/span>size<\/span> <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n            <\/span>throw<\/span> <\/span>new<\/span> InvalidOperationException<\/span>(<\/span>"<\/span>Heap is empty.<\/span>"<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>int<\/span> max <\/span>=<\/span> <\/span>heap<\/span>[<\/span>0<\/span>]<\/span>;<\/span><\/span>\n        <\/span>heap<\/span>[<\/span>0<\/span>]<\/span> <\/span>=<\/span> <\/span>heap<\/span>[<\/span>size<\/span> <\/span>-<\/span> <\/span>1<\/span>]<\/span>;<\/span><\/span>\n        <\/span>size<\/span>--;<\/span><\/span>\n<\/span>\n        <\/span>Heapify<\/span>(<\/span>0<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> <\/span>max<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>HeapSort<\/span>()<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> i <\/span>=<\/span> <\/span>size<\/span> <\/span>\/<\/span> <\/span>2<\/span> <\/span>-<\/span> <\/span>1<\/span>;<\/span> <\/span>i<\/span> <\/span>>=<\/span> <\/span>0<\/span>;<\/span> <\/span>i<\/span>--<\/span>)<\/span><\/span>\n            <\/span>Heapify<\/span>(<\/span>i<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> i <\/span>=<\/span> <\/span>size<\/span> <\/span>-<\/span> <\/span>1<\/span>;<\/span> <\/span>i<\/span> <\/span>>=<\/span> <\/span>0<\/span>;<\/span> <\/span>i<\/span>--<\/span>)<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>Swap<\/span>(<\/span>0<\/span>,<\/span> <\/span>i<\/span>)<\/span>;<\/span><\/span>\n            <\/span>Heapify<\/span>(<\/span>0<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>Program<\/span><\/span>\n{<\/span><\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>Main<\/span>()<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>int<\/span>[]<\/span> array <\/span>=<\/span> <\/span>{<\/span> <\/span>7<\/span>,<\/span> <\/span>3<\/span>,<\/span> <\/span>9<\/span>,<\/span> <\/span>2<\/span>,<\/span> <\/span>4<\/span>,<\/span> <\/span>1<\/span>,<\/span> <\/span>5<\/span> <\/span>}<\/span>;<\/span><\/span>\n<\/span>\n        BinaryHeap heap <\/span>=<\/span> <\/span>new<\/span> BinaryHeap<\/span>(<\/span>array<\/span>.<\/span>Length<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>foreach<\/span> <\/span>(<\/span>int<\/span> num <\/span>in<\/span> <\/span>array<\/span>)<\/span><\/span>\n            <\/span>heap<\/span>.<\/span>Insert<\/span>(<\/span>num<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>Console<\/span>.<\/span>WriteLine<\/span>(<\/span>"<\/span>Original array:<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>foreach<\/span> <\/span>(<\/span>int<\/span> num <\/span>in<\/span> <\/span>array<\/span>)<\/span><\/span>\n            <\/span>Console<\/span>.<\/span>Write<\/span>(<\/span>num<\/span> <\/span>+<\/span> <\/span>"<\/span> <\/span>"<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>heap<\/span>.<\/span>HeapSort<\/span>()<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>Console<\/span>.<\/span>WriteLine<\/span>(<\/span>"<\/span>\\n\\n<\/span>Sorted array:<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>while<\/span> <\/span>(<\/span>heap<\/span>.<\/span>Size<\/span> <\/span>><\/span> <\/span>0<\/span>)<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>int<\/span> max <\/span>=<\/span> <\/span>heap<\/span>.<\/span>RemoveMax<\/span>()<\/span>;<\/span><\/span>\n            <\/span>Console<\/span>.<\/span>Write<\/span>(<\/span>max<\/span> <\/span>+<\/span> <\/span>"<\/span> <\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
O c\u00f3digo apresentado implementa um Binary Heap e utiliza o algoritmo HeapSort para classificar um array de inteiros em ordem crescente. Vamos entender como funciona:<\/p>\n\n\n\n
    \n
  • A classe BinaryHeap<\/code> representa a estrutura do Binary Heap. Ela possui um array interno chamado heap<\/code> que armazena os elementos e uma vari\u00e1vel size<\/code> que controla o n\u00famero de elementos atualmente no heap.<\/li>\n\n\n\n
  • O m\u00e9todo Heapify<\/code> \u00e9 respons\u00e1vel por manter a propriedade de heap no Binary Heap. Ele compara o elemento atual com seus filhos e, se necess\u00e1rio, realiza trocas para garantir que o maior elemento esteja na posi\u00e7\u00e3o correta.<\/li>\n\n\n\n
  • O m\u00e9todo Insert<\/code> \u00e9 usado para inserir um novo elemento no Binary Heap. Ele adiciona o elemento no final do array e realiza uma s\u00e9rie de trocas para posicionar o elemento na posi\u00e7\u00e3o correta de acordo com a propriedade de heap.<\/li>\n\n\n\n
  • O m\u00e9todo RemoveMax<\/code> remove o elemento m\u00e1ximo (raiz) do Binary Heap e o substitui pelo \u00faltimo elemento do heap. Em seguida, ele chama o m\u00e9todo Heapify<\/code> para restaurar a propriedade de heap.<\/li>\n\n\n\n
  • O m\u00e9todo HeapSort<\/code> utiliza o Binary Heap para ordenar o array. Primeiro, ele constr\u00f3i o heap a partir dos elementos do array. Em seguida, repetidamente extrai o elemento m\u00e1ximo (raiz) do heap, realiza a troca com o \u00faltimo elemento n\u00e3o classificado e reconstitui o heap. Esse processo \u00e9 repetido at\u00e9 que todos os elementos estejam classificados em ordem crescente.<\/li>\n\n\n\n
  • No m\u00e9todo Main<\/code>, um array de inteiros \u00e9 criado e inserido no Binary Heap. Em seguida, o algoritmo HeapSort \u00e9 aplicado ao heap, resultando em um array ordenado. O array original e o array ordenado s\u00e3o exibidos no console.<\/li>\n<\/ul>\n\n\n\n
    Exemplo de implementa\u00e7\u00e3o em Java<\/h3>\n\n\n\n
    Java<\/span><\/path><\/path><\/svg><\/span>
    import<\/span> <\/span>java<\/span>.<\/span>util<\/span>.<\/span>Arrays<\/span>;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>BinaryHeapHeapSortExample<\/span> <\/span>{<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[]<\/span> <\/span>heap<\/span>;<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span> <\/span>size<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>BinaryHeapHeapSortExample<\/span>(<\/span>int<\/span> <\/span>capacity<\/span>)<\/span> <\/span>{<\/span><\/span>\n        heap <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>capacity<\/span>]<\/span>;<\/span><\/span>\n        size <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>void<\/span> <\/span>heapify<\/span>(<\/span>int<\/span> <\/span>index<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span> <\/span>largest<\/span> <\/span>=<\/span> index<\/span>;<\/span><\/span>\n        <\/span>int<\/span> <\/span>leftChild<\/span> <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> index <\/span>+<\/span> <\/span>1<\/span>;<\/span><\/span>\n        <\/span>int<\/span> <\/span>rightChild<\/span> <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> index <\/span>+<\/span> <\/span>2<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> <\/span>(<\/span>leftChild <\/span><<\/span> size <\/span>&&<\/span> heap<\/span>[<\/span>leftChild<\/span>]<\/span> <\/span>><\/span> heap<\/span>[<\/span>largest<\/span>])<\/span><\/span>\n            largest <\/span>=<\/span> leftChild<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> <\/span>(<\/span>rightChild <\/span><<\/span> size <\/span>&&<\/span> heap<\/span>[<\/span>rightChild<\/span>]<\/span> <\/span>><\/span> heap<\/span>[<\/span>largest<\/span>])<\/span><\/span>\n            largest <\/span>=<\/span> rightChild<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> <\/span>(<\/span>largest <\/span>!=<\/span> index<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>swap<\/span>(<\/span>index<\/span>,<\/span> largest<\/span>)<\/span>;<\/span><\/span>\n            <\/span>heapify<\/span>(<\/span>largest<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>void<\/span> <\/span>swap<\/span>(<\/span>int<\/span> <\/span>i<\/span>,<\/span> <\/span>int<\/span> <\/span>j<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span> <\/span>temp<\/span> <\/span>=<\/span> heap<\/span>[<\/span>i<\/span>]<\/span>;<\/span><\/span>\n        heap<\/span>[<\/span>i<\/span>]<\/span> <\/span>=<\/span> heap<\/span>[<\/span>j<\/span>]<\/span>;<\/span><\/span>\n        heap<\/span>[<\/span>j<\/span>]<\/span> <\/span>=<\/span> temp<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>insert<\/span>(<\/span>int<\/span> <\/span>value<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>if<\/span> <\/span>(<\/span>size <\/span>==<\/span> <\/span>heap<\/span>.<\/span>length<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>throw<\/span> <\/span>new<\/span> <\/span>IllegalStateException<\/span>(<\/span>"<\/span>Heap is full<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>int<\/span> <\/span>index<\/span> <\/span>=<\/span> size<\/span>;<\/span><\/span>\n        heap<\/span>[<\/span>index<\/span>]<\/span> <\/span>=<\/span> value<\/span>;<\/span><\/span>\n        size<\/span>++;<\/span><\/span>\n<\/span>\n        <\/span>while<\/span> <\/span>(<\/span>index <\/span>><\/span> <\/span>0<\/span> <\/span>&&<\/span> heap<\/span>[<\/span>index<\/span>]<\/span> <\/span>><\/span> heap<\/span>[<\/span>parent<\/span>(<\/span>index<\/span>)])<\/span> <\/span>{<\/span><\/span>\n            <\/span>swap<\/span>(<\/span>index<\/span>,<\/span> <\/span>parent<\/span>(<\/span>index<\/span>))<\/span>;<\/span><\/span>\n            index <\/span>=<\/span> <\/span>parent<\/span>(<\/span>index<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>int<\/span> <\/span>parent<\/span>(<\/span>int<\/span> <\/span>index<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>return<\/span> <\/span>(<\/span>index <\/span>-<\/span> <\/span>1<\/span>)<\/span> <\/span>\/<\/span> <\/span>2<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>removeMax<\/span>()<\/span> <\/span>{<\/span><\/span>\n        <\/span>if<\/span> <\/span>(<\/span>size <\/span>==<\/span> <\/span>0<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>throw<\/span> <\/span>new<\/span> <\/span>IllegalStateException<\/span>(<\/span>"<\/span>Heap is empty<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        heap<\/span>[<\/span>0<\/span>]<\/span> <\/span>=<\/span> heap<\/span>[<\/span>size <\/span>-<\/span> <\/span>1<\/span>]<\/span>;<\/span><\/span>\n        size<\/span>--;<\/span><\/span>\n        <\/span>heapify<\/span>(<\/span>0<\/span>)<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>heapSort<\/span>()<\/span> <\/span>{<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>i<\/span> <\/span>=<\/span> size <\/span>\/<\/span> <\/span>2<\/span> <\/span>-<\/span> <\/span>1<\/span>;<\/span> i <\/span>>=<\/span> <\/span>0<\/span>;<\/span> i<\/span>--<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>heapify<\/span>(<\/span>i<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>i<\/span> <\/span>=<\/span> size <\/span>-<\/span> <\/span>1<\/span>;<\/span> i <\/span>>=<\/span> <\/span>0<\/span>;<\/span> i<\/span>--<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>swap<\/span>(<\/span>0<\/span>,<\/span> i<\/span>)<\/span>;<\/span><\/span>\n            <\/span>heapify<\/span>(<\/span>0<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[]<\/span> <\/span>args<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span>[]<\/span> <\/span>array<\/span> <\/span>=<\/span> <\/span>{<\/span> <\/span>4<\/span>,<\/span> <\/span>10<\/span>,<\/span> <\/span>3<\/span>,<\/span> <\/span>5<\/span>,<\/span> <\/span>1<\/span> <\/span>}<\/span>;<\/span><\/span>\n        <\/span>BinaryHeapHeapSortExample<\/span> <\/span>binaryHeap<\/span> <\/span>=<\/span> <\/span>new<\/span> <\/span>BinaryHeapHeapSortExample<\/span>(<\/span>array<\/span>.<\/span>length<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>value<\/span> <\/span>:<\/span> array<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>binaryHeap<\/span>.<\/span>insert<\/span>(<\/span>value<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>"<\/span>Original array: <\/span>"<\/span> <\/span>+<\/span> <\/span>Arrays<\/span>.<\/span>toString<\/span>(<\/span>array<\/span>))<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>binaryHeap<\/span>.<\/span>heapSort<\/span>()<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>"<\/span>Sorted array: <\/span>"<\/span> <\/span>+<\/span> <\/span>Arrays<\/span>.<\/span>toString<\/span>(<\/span>binaryHeap<\/span>.<\/span>heap<\/span>))<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
    O c\u00f3digo em Java apresenta a implementa\u00e7\u00e3o de um Binary Heap e utiliza o algoritmo HeapSort para classificar um array de inteiros em ordem crescente. Vamos entender a l\u00f3gica principal do c\u00f3digo:<\/p>\n\n\n\n
      \n
    1. A classe BinaryHeapHeapSortExample<\/code> possui um array heap<\/code> que representa o Binary Heap e uma vari\u00e1vel size<\/code> que indica o n\u00famero de elementos presentes no heap.<\/li>\n\n\n\n
    2. O m\u00e9todo heapify<\/code> \u00e9 respons\u00e1vel por garantir a propriedade de heap, ou seja, a ordena\u00e7\u00e3o dos elementos no heap. Ele compara o n\u00f3 atual com seus filhos e faz as trocas necess\u00e1rias para manter a ordena\u00e7\u00e3o correta.<\/li>\n\n\n\n
    3. O m\u00e9todo insert<\/code> insere um novo valor no heap. Ele adiciona o valor ao final do array e realiza trocas com o pai, se necess\u00e1rio, para manter a propriedade de heap.<\/li>\n\n\n\n
    4. O m\u00e9todo removeMax<\/code> remove o maior elemento do heap, que \u00e9 sempre o primeiro elemento (\u00edndice 0). Ele substitui o primeiro elemento pelo \u00faltimo elemento do array e chama o m\u00e9todo heapify<\/code> para reorganizar o heap.<\/li>\n\n\n\n
    5. O m\u00e9todo heapSort<\/code> aplica o algoritmo HeapSort. Ele constr\u00f3i o heap a partir dos elementos do array, troca repetidamente o elemento m\u00e1ximo (\u00edndice 0) com o \u00faltimo elemento n\u00e3o ordenado e chama o m\u00e9todo heapify<\/code> para reorganizar o heap.<\/li>\n\n\n\n
    6. No m\u00e9todo main<\/code>, \u00e9 criado um array de inteiros e um objeto BinaryHeapHeapSortExample<\/code>. Os valores do array s\u00e3o inseridos no heap e, em seguida, o algoritmo HeapSort \u00e9 aplicado. Os arrays original e ordenado s\u00e3o exibidos no console.<\/li>\n<\/ol>\n\n\n\n
      Exemplo de implementa\u00e7\u00e3o em Python<\/p>\n\n\n\n
      Python<\/span><\/path><\/path><\/svg><\/span>
      class<\/span> <\/span>BinaryHeapHeapSortExample<\/span>:<\/span><\/span>\n    <\/span>def<\/span> <\/span>__init__<\/span>(<\/span>self<\/span>):<\/span><\/span>\n        <\/span>self<\/span>.<\/span>heap <\/span>=<\/span> <\/span>[]<\/span><\/span>\n    <\/span><\/span>\n    <\/span>def<\/span> <\/span>heapify<\/span>(<\/span>self<\/span>,<\/span> <\/span>n<\/span>,<\/span> <\/span>i<\/span>):<\/span><\/span>\n        largest <\/span>=<\/span> i<\/span><\/span>\n        left <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> i <\/span>+<\/span> <\/span>1<\/span><\/span>\n        right <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> i <\/span>+<\/span> <\/span>2<\/span><\/span>\n        <\/span><\/span>\n        <\/span>if<\/span> left <\/span><<\/span> n <\/span>and<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>left<\/span>]<\/span> <\/span>><\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>largest<\/span>]:<\/span><\/span>\n            largest <\/span>=<\/span> left<\/span><\/span>\n        <\/span><\/span>\n        <\/span>if<\/span> right <\/span><<\/span> n <\/span>and<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>right<\/span>]<\/span> <\/span>><\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>largest<\/span>]:<\/span><\/span>\n            largest <\/span>=<\/span> right<\/span><\/span>\n        <\/span><\/span>\n        <\/span>if<\/span> largest <\/span>!=<\/span> i<\/span>:<\/span><\/span>\n            <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>i<\/span>],<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>largest<\/span>]<\/span> <\/span>=<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>largest<\/span>],<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>i<\/span>]<\/span><\/span>\n            <\/span>self<\/span>.<\/span>heapify<\/span>(<\/span>n<\/span>,<\/span> largest<\/span>)<\/span><\/span>\n    <\/span><\/span>\n    <\/span>def<\/span> <\/span>insert<\/span>(<\/span>self<\/span>,<\/span> <\/span>value<\/span>):<\/span><\/span>\n        <\/span>self<\/span>.<\/span>heap<\/span>.<\/span>append<\/span>(<\/span>value<\/span>)<\/span><\/span>\n        n <\/span>=<\/span> <\/span>len<\/span>(<\/span>self<\/span>.<\/span>heap<\/span>)<\/span><\/span>\n        i <\/span>=<\/span> n <\/span>\/\/<\/span> <\/span>2<\/span> <\/span>-<\/span> <\/span>1<\/span><\/span>\n        <\/span><\/span>\n        <\/span>while<\/span> i <\/span>>=<\/span> <\/span>0<\/span>:<\/span><\/span>\n            <\/span>self<\/span>.<\/span>heapify<\/span>(<\/span>n<\/span>,<\/span> i<\/span>)<\/span><\/span>\n            i <\/span>-=<\/span> <\/span>1<\/span><\/span>\n    <\/span><\/span>\n    <\/span>def<\/span> <\/span>remove_max<\/span>(<\/span>self<\/span>):<\/span><\/span>\n        n <\/span>=<\/span> <\/span>len<\/span>(<\/span>self<\/span>.<\/span>heap<\/span>)<\/span><\/span>\n        <\/span><\/span>\n        <\/span>if<\/span> n <\/span>==<\/span> <\/span>0<\/span>:<\/span><\/span>\n            <\/span>return<\/span> <\/span>None<\/span><\/span>\n        <\/span><\/span>\n        max_value <\/span>=<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>0<\/span>]<\/span><\/span>\n        <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>0<\/span>]<\/span> <\/span>=<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>n <\/span>-<\/span> <\/span>1<\/span>]<\/span><\/span>\n        <\/span>self<\/span>.<\/span>heap<\/span>.<\/span>pop<\/span>()<\/span><\/span>\n        <\/span>self<\/span>.<\/span>heapify<\/span>(<\/span>n <\/span>-<\/span> <\/span>1<\/span>,<\/span> <\/span>0<\/span>)<\/span><\/span>\n        <\/span><\/span>\n        <\/span>return<\/span> max_value<\/span><\/span>\n    <\/span><\/span>\n    <\/span>def<\/span> <\/span>heap_sort<\/span>(<\/span>self<\/span>):<\/span><\/span>\n        n <\/span>=<\/span> <\/span>len<\/span>(<\/span>self<\/span>.<\/span>heap<\/span>)<\/span><\/span>\n        <\/span><\/span>\n        <\/span>for<\/span> i <\/span>in<\/span> <\/span>range<\/span>(<\/span>n <\/span>\/\/<\/span> <\/span>2<\/span> <\/span>-<\/span> <\/span>1<\/span>,<\/span> <\/span>-<\/span>1<\/span>,<\/span> <\/span>-<\/span>1<\/span>):<\/span><\/span>\n            <\/span>self<\/span>.<\/span>heapify<\/span>(<\/span>n<\/span>,<\/span> i<\/span>)<\/span><\/span>\n        <\/span><\/span>\n        <\/span>for<\/span> i <\/span>in<\/span> <\/span>range<\/span>(<\/span>n <\/span>-<\/span> <\/span>1<\/span>,<\/span> <\/span>0<\/span>,<\/span> <\/span>-<\/span>1<\/span>):<\/span><\/span>\n            <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>i<\/span>],<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>0<\/span>]<\/span> <\/span>=<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>0<\/span>],<\/span> <\/span>self<\/span>.<\/span>heap<\/span>[<\/span>i<\/span>]<\/span><\/span>\n            <\/span>self<\/span>.<\/span>heapify<\/span>(<\/span>i<\/span>,<\/span> <\/span>0<\/span>)<\/span><\/span>\n    <\/span><\/span>\n<\/span>\nif<\/span> __name__ <\/span>==<\/span> <\/span>"<\/span>__main__<\/span>"<\/span>:<\/span><\/span>\n    array <\/span>=<\/span> <\/span>[<\/span>12<\/span>,<\/span> <\/span>11<\/span>,<\/span> <\/span>13<\/span>,<\/span> <\/span>5<\/span>,<\/span> <\/span>6<\/span>,<\/span> <\/span>7<\/span>]<\/span><\/span>\n    heap_sort_example <\/span>=<\/span> <\/span>BinaryHeapHeapSortExample<\/span>()<\/span><\/span>\n    <\/span><\/span>\n    <\/span>for<\/span> num <\/span>in<\/span> array<\/span>:<\/span><\/span>\n        heap_sort_example<\/span>.<\/span>insert<\/span>(<\/span>num<\/span>)<\/span><\/span>\n    <\/span><\/span>\n    <\/span>print<\/span>(<\/span>"<\/span>Array original:<\/span>"<\/span>,<\/span> array<\/span>)<\/span><\/span>\n    <\/span><\/span>\n    heap_sort_example<\/span>.<\/span>heap_sort<\/span>()<\/span><\/span>\n    <\/span><\/span>\n    sorted_array <\/span>=<\/span> <\/span>[<\/span>heap_sort_example<\/span>.<\/span>remove_max<\/span>()<\/span> <\/span>for<\/span> _ <\/span>in<\/span> <\/span>range<\/span>(<\/span>len<\/span>(<\/span>array<\/span>))]<\/span><\/span>\n    <\/span><\/span>\n    <\/span>print<\/span>(<\/span>"<\/span>Array ordenado:<\/span>"<\/span>,<\/span> sorted_array<\/span>)<\/span><\/span>\n<\/span>\n# Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
      Neste c\u00f3digo Python, a classe BinaryHeapHeapSortExample<\/code> implementa um Binary Heap e utiliza o algoritmo HeapSort para classificar um array de inteiros em ordem crescente.<\/p>\n\n\n\n
      A l\u00f3gica do c\u00f3digo \u00e9 semelhante \u00e0 implementa\u00e7\u00e3o em Java, utilizando m\u00e9todos como heapify<\/code>, insert<\/code>, remove_max<\/code> e heap_sort<\/code> para manipular o heap e realizar a ordena\u00e7\u00e3o.<\/p>\n\n\n\n
      No exemplo principal, \u00e9 criado um array de inteiros e um objeto BinaryHeapHeapSortExample<\/code>. Os valores do array s\u00e3o inseridos no heap e, em seguida, o algoritmo HeapSort \u00e9 aplicado. Os arrays original e ordenado s\u00e3o exibidos no console.<\/p>\n\n\n\n
      Conclus\u00e3o<\/h2>\n\n\n\n
      Compreender Binary Heap <\/em>e HeapSort <\/em>\u00e9 fundamental para qualquer pessoa interessada em algoritmos e estruturas de dados. Com sua efici\u00eancia e versatilidade, esses conceitos s\u00e3o essenciais para resolver problemas complexos de forma eficiente.<\/p>\n\n\n\n
      Esse conte\u00fado \u00e9 parte do material disponibilizado para os participantes do meu grupo de estudos de\u00a0Algoritmos e Estruturas de Dados. Voc\u00ea quer participar desse grupo?\u00a0Clique aqui e veja como funciona<\/strong><\/a>.<\/p>\n\n\n\n
      D\u00favidas Frequentes<\/h2>\n\n\n\n
      O que \u00e9 Binary Heap<\/em>?<\/strong>
      Binary Heap<\/em> \u00e9 uma estrutura de dados que representa uma \u00e1rvore bin\u00e1ria completa.<\/p>\n\n\n\n
      O que s\u00e3o Max Heap<\/em> e Min Heap<\/em>?<\/strong>
      S\u00e3o duas varia\u00e7\u00f5es de Binary Heap<\/em>. No Max Heap<\/em>, os pais t\u00eam valores maiores que ou iguais aos dos filhos, enquanto no Min Heap<\/em>, os pais t\u00eam valores menores que ou iguais aos dos filhos.<\/p>\n\n\n\n
      O que \u00e9 HeapSort<\/em>?<\/strong>
      HeapSort<\/em> \u00e9 um algoritmo de ordena\u00e7\u00e3o que utiliza um Binary Heap<\/em> para ordenar os elementos.<\/p>\n\n\n\n
      Qual a complexidade de tempo do HeapSort<\/em>?<\/strong>
      A complexidade de tempo do HeapSort<\/em> \u00e9 O(n log n)<\/em>, tornando-o eficiente para a ordena\u00e7\u00e3o de grandes conjuntos de dados.<\/p>\n\n\n\n
      Onde o Binary Heap<\/em> e o HeapSort<\/em> s\u00e3o aplicados?<\/strong>
      Eles s\u00e3o aplicados em muitas \u00e1reas, como sistemas de banco de dados, simula\u00e7\u00e3o de eventos discretos e algoritmos de caminho mais curto.<\/p>\n","protected":false},"featured_media":4778,"parent":0,"template":"","cursos":[5],"class_list":["post-4775","artigos","type-artigos","status-publish","has-post-thumbnail","hentry","cursos-algortimos"],"acf":[],"_links":{"self":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos\/4775","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos"}],"about":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/types\/artigos"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media\/4778"}],"wp:attachment":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media?parent=4775"}],"wp:term":[{"taxonomy":"cursos","embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/cursos?post=4775"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}