Scribd
Upload
11 views8 pages

Understanding K-ary Heaps in Java

K-ary heaps generalize binary heaps by allowing each node to have K children, maintaining properties of a nearly complete binary tree. They can be categorized into max k-ary heaps and min k-ary heaps based on the relationship of the root key with its descendants. The document also includes Java code demonstrating the implementation of k-ary heaps, including methods for building the heap, inserting elements, and extracting the maximum value.

Uploaded by

Vaishnavi Chenikkayala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
11 views8 pages

Understanding K-ary Heaps in Java

K-ary heaps generalize binary heaps by allowing each node to have K children, maintaining properties of a nearly complete binary tree. They can be categorized into max k-ary heaps and min k-ary heaps based on the relationship of the root key with its descendants. The document also includes Java code demonstrating the implementation of k-ary heaps, including methods for building the heap, inserting elements, and extracting the maximum value.

Uploaded by

Vaishnavi Chenikkayala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 8

K-ary Heap

K – ary heap
K-ary heaps are a generalization of binary heap(K=2) in which each node have K children
instead of 2. Just like binary heap, it follows two properties:

1. Nearly complete binary tree, with all levels having maximum number of nodes except the
last, which is filled in left to right manner.

2. Like Binary Heap, it can be divided into two categories:

• Max k-ary heap (key at root is greater than all descendants and same is recursively
true for all nodes).
• Min k-ary heap (key at root is lesser than all descendants and same is recursively
true for all nodes)
1 public class Main {
2 public static void main(String[] args) {
3 final int capacity = 100;
4 int[] arr = new int[capacity];
5 arr[0] = 4;
6 arr[1] = 5;
7 arr[2] = 6;
8 arr[3] = 7;
9 arr[4] = 8;
10 arr[5] = 9;
11 arr[6] = 10;
12 int n = 7;
13 int k = 3;
14 buildHeap(arr, n, k);
15 System.out.println("Built Heap: ");
16 for (int i = 0; i < n; i++)
17 System.out.print(arr[i] + " ");
18 int element = 3;
19 insert(arr, n, k, element);
20 n++;
21
22
23 System.out.println("Heap after insertion of " +element + ": ");
24 for (int i = 0; i < n; i++)
25 System.out.print(arr[i] + " ");
26 System.out.println("Extracted max is "
27 +extractMax(arr,n,k));
28 n--;
29 System.out.println("\n\nHeap after extract max: ");
30 for (int i = 0; i < n; i++)
31 System.out.print(arr[i] + " ");
32 }
33 public static void buildHeap(int[] arr, int n, int k) {
34 for (int i = (n - 1) / k; i >= 0; i--)
35 restoreDown(arr, n, i, k);
36 }
37 public static void insert(int[] arr, int n, int k, int elem) {
38 arr[n - 1] = elem;
39 restoreUp(arr, n - 1, k);
40 }
41 public static int extractMax(int[] arr, int n, int k) {
42 int max = arr[0];arr[0] = arr[n - 1];
43 restoreDown(arr, n - 1, 0, k);
44 return max;
45 public static void restoreDown(int[] arr, int len, int index, int k){
46 int[] child = new int[k + 1];
47 while (true) {
48 for (int i = 1; i <= k; i++)
49 child[i]=(k*index+i) < len ? (k*index+i) : -1;
50 int maxChild = -1, maxChildIndex = 0;
51 for (int i = 1; i <= k; i++) {
52 if (child[i] != -1 && arr[child[i]] > maxChild) {
53 maxChildIndex = child[i];
54 maxChild = arr[child[i]];
55 }
56 }
57 if (maxChild == -1)
58 break;
59 if (arr[index] < arr[maxChildIndex])
60 swap(arr, index, maxChildIndex);
61 index = maxChildIndex;
62 }
63 }
64
65
66
67 public static void restoreUp(int[] arr, int index, int k) {
68 int parent = (index - 1) / k;
69 while (parent >= 0) {
70 if (arr[index] > arr[parent]) {
71 swap(arr, index, parent);
72 index = parent;
73 parent = (index - 1) / k;
74 } else
75 break;
76 }
77 }
78 public static void swap(int[] arr, int i, int j) {
79 int temp = arr[i];
80 arr[i] = arr[j];
81 arr[j] = temp;
82 }
83 }
84
85
86
87
88
THANK YOU

You might also like