Java >> Java opplæring >  >> Java

Max Heap Java-eksempel

I denne artikkelen vil vi vise hva som er max heap i Java og hvorfor vi bruker det.

1. Introduksjon

Et binærtre med maksimal haug er et komplett binært tre der verdien til hver node er mindre enn eller lik verdien til dens overordnede, med maksimumsverdielementet ved roten. En typisk representasjon av et Max-heap binært tre er som følger:

1.1 Matrisepresentasjon av det binære treet

Dette er et komplett binært tre og er vanligvis representert som en matrise. Rotelementet er betegnet med Arr[0]. Følgende liste viser arrayrepresentasjonen av de tilknyttede nodene til en gitt node, dvs. Arr[i] i et binært tre med maksimal haug:

  • Arr[(i-1)/2] representerer den overordnede noden.
  • Arr[(2*i)+1] representerer den venstre underordnede noden.
  • Arr[(2*i)+2] representerer den høyre underordnede noden.

1.2 Operasjoner i heap binært tre

Operasjonene som utføres på et binært haugtre er listet opp nedenfor:

  • Peek(): Den returnerer rotelementet. Dette er det maksimale elementet av heap. Tidskompleksiteten til denne operasjonen er O(1).
  • Poll(): Fjerner maksimumselementet fra MaxHeap. Tidskompleksiteten til denne operasjonen er O(Logn) siden denne operasjonen trenger å opprettholde heap-egenskapen (ved å kalle heapify()) etter at roten er fjernet.
  • add(): Å sette inn en ny nøkkel tar O(Logn) tid. Vi legger til en ny nøkkel i enden av treet. Hvis en ny nøkkel er mindre enn forelderen, trenger vi ikke å gjøre noe. Ellers må vi krysse opp for å fikse den krenkede haugeiendommen.

2. Java-implementeringen

Vi vil nå se et demoeksempel for Max-heap binærtreet ved å bruke Java og forstå hvordan de forskjellige operasjonene fungerer på det.

// Java program to implement Max Heap 
public class MaxHeap { 
    private int[] Heap; 
    private int size; 
    private int maxsize; 
  
    // Constructor to initialize an 
    // empty max heap with given maximum 
    // capacity. 
    public MaxHeap(int maxsize) 
    { 
        this.maxsize = maxsize; 
        this.size = 0; 
        Heap = new int[this.maxsize + 1]; 
        Heap[0] = Integer.MAX_VALUE; 
    } 
  
    // Returns position of parent 
    private int parent(int pos) 
    { 
        return pos / 2; 
    } 
  
    // Below two functions return left and 
    // right children. 
    private int leftChild(int pos) 
    { 
        return (2 * pos); 
    } 
    private int rightChild(int pos) 
    { 
        return (2 * pos) + 1; 
    } 
  
    // Returns true of given node is leaf 
    private boolean isLeaf(int pos) 
    { 
        if (pos >= (size / 2) && pos <= size) { 
            return true; 
        } 
        return false; 
    } 
  
    private void swap(int fpos, int spos) 
    { 
        int tmp; 
        tmp = Heap[fpos]; 
        Heap[fpos] = Heap[spos]; 
        Heap[spos] = tmp; 
    } 
  
    // A recursive function to max heapify the given 
    // subtree. This function assumes that the left and 
    // right subtrees are already heapified, we only need 
    // to fix the root. 
    private void maxHeapify(int pos) 
    { 
        if (isLeaf(pos)) 
            return; 
  
        if (Heap[pos] < Heap[leftChild(pos)] ||  
            Heap[pos] < Heap[rightChild(pos)]) { 
  
            if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) { 
                swap(pos, leftChild(pos)); 
                maxHeapify(leftChild(pos)); 
            } 
            else { 
                swap(pos, rightChild(pos)); 
                maxHeapify(rightChild(pos)); 
            } 
        } 
    } 
  
    // Inserts a new element to max heap 
    public void add(int element) 
    { 
        Heap[++size] = element; 
  
        // Traverse up and fix violated property 
        int current = size; 
        while (Heap[current] > Heap[parent(current)]) { 
            swap(current, parent(current)); 
            current = parent(current); 
        } 
    } 
  
    public void display() 
    { 
        for (int i = 1; i <= size / 2; i++) { 
            System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + 
                      Heap[2 * i] + " RIGHT CHILD :" + Heap[2 * i + 1]); 
            System.out.println(); 
        } 
    } 
  
    // Remove an element from max heap 
    public int poll() 
    { 
        int popped = Heap[1]; 
        Heap[1] = Heap[size--]; 
        maxHeapify(1); 
        return popped; 
    } 
  
    public static void main(String[] arg) 
    { 
        System.out.println("The Max Heap is "); 
        MaxHeap maxHeap = new MaxHeap(20); 
        maxHeap.add(15); 
        maxHeap.add(13); 
        maxHeap.add(7); 
        maxHeap.add(5); 
        maxHeap.add(52); 
        maxHeap.add(23); 
        maxHeap.add(16); 
        maxHeap.add(9); 
        maxHeap.add(21); 
  
        maxHeap.display(); 
        System.out.println("The max val is " + maxHeap.poll()); 
    } 
}
Utgang
The Max Heap is 
 PARENT : 52 LEFT CHILD : 21 RIGHT CHILD :23
 PARENT : 21 LEFT CHILD : 15 RIGHT CHILD :13
 PARENT : 23 LEFT CHILD : 7 RIGHT CHILD :16
 PARENT : 15 LEFT CHILD : 5 RIGHT CHILD :9
The max val is 52

3. Max Heap brukt som en prioritert kø

Prioritetskø er en abstrakt datastruktur som ligner på en vanlig kø eller en stabeldatastruktur der hvert element har et tilleggsfelt kjent som Prioritet knyttet til seg og serveres basert på dets prioritet. I Java kan dette brukes som en prioritert kø som vi vil se i følgende demo.

// Java program to demonstrate working of PriorityQueue as a Max Heap 
import java.util.*; 
  
class PriorityQueueDemo { 
  public static void main(String args[]) 
    { 
        // Creating empty priority queue 
        PriorityQueue<Integer> pQueue =  new PriorityQueue<Integer>(Collections.reverseOrder()); 
  
        // Adding items to the pQueue using add() 
        pQueue.add(50); 
        pQueue.add(30); 
        pQueue.add(20); 
        pQueue.add(10); 
  
        // Displaying the highest priority element 
        System.out.println("Head value using peek function:" +  pQueue.peek()); 
  
        // Printing all elements 
        System.out.println("The queue elements:"); 
        Iterator itr = pQueue.iterator(); 
        while (itr.hasNext()) 
            System.out.println(itr.next()); 
  
        // Removing the top priority element (or head) and 
        // printing the modified pQueue using poll() 
        pQueue.poll(); 
        System.out.println("After removing an element with poll function:"); 
        Iterator<Integer> itr2 = pQueue.iterator(); 
        while (itr2.hasNext()) 
            System.out.println(itr2.next()); 
  
        // Removing element 20 using remove() 
        pQueue.remove(20); 
        System.out.println("after removing 20 with remove function:"); 
        Iterator<Integer> itr3 = pQueue.iterator(); 
        while(itr3.hasNext()) 
            System.out.println(itr3.next()); 
  
        // Check if an element is present using contains() 
        boolean b = pQueue.contains(20); 
        System.out.println("Priority queue contains 20 or not?: " + b); 
  
        // Getting objects from the queue using toArray() in an array and display the array 
        Object[] arr = pQueue.toArray(); 
        System.out.println("Value in array: "); 
        for(int i = 0; i < arr.length; i++) 
            System.out.println("Value: " + arr[i].toString()); 
    } 
} 
Utgang
Head value using peek function:50
The queue elements:
50
30
20
10
After removing an element with poll function:
30
10
20
after removing 20 with remove function:
30
10
Priority queue contains 20 or not?: false
Value in array: 
Value: 30
Value: 10

4. Anvendelser av Max Heap Binary Tree

Max Heap Binært tre kan brukes i forskjellige områder av datastruktur, hvorav noen er uthevet nedenfor:

  • Hapesortering: Heap Sort bruker Binary Heap til å sortere en matrise i O(nLogn) tid.
  • Prioritetskø: Prioritetskøer kan implementeres effektivt ved å bruke Binary Heap fordi den støtter insert(), delete() og pop(), reductionKey() operasjoner i O(logging)-tid. Binomial Heap og Fibonacci Heap er varianter av Binary Heap. Disse variasjonene utfører fagforeninger også effektivt.
  • Mange datastrukturproblemer kan løses effektivt ved hjelp av Max-Heaps. Se for eksempel følgende. en. K’th største element i en matrise.

5. Konklusjon

I denne opplæringen forsto vi definisjonen og implementeringen av det binære treet i Java, og vi forsto også hvordan det kan brukes til å løse mange datastrukturproblemer som Priority Queue og Finding Kth største element i en matrise.

6. Referanser

  • https://www.geeksforgeeks.org/binary-heap/
  • http://www.btechsmartclass.com/data_structures/max-heap.html
  • https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm
  • https://www.educative.io/edpresso/min-heap-vs-max-heap

Følgende kode viser bruken av Max Heap Binary-treet og implementeringen av det som en prioritert kø.

Java Tag