Binomial Algorithm
The Binomial Heap Algorithm is a powerful data structure used for designing efficient priority queues, which are essential for solving various computational problems. Binomial heaps are a collection of binomial trees that are ordered as per the binomial distribution, where each tree follows the min-heap property (i.e., the parent node has a smaller key value than its children nodes). The core idea behind binomial heaps is to merge binomial trees of the same order to create a new binomial tree with an increased order, thus enabling fast insertion, deletion, and merging operations.
The primary operations supported by the binomial heap algorithm are insertion, deletion, union (merging), and finding the minimum element. When inserting an element, the algorithm creates a new binomial tree of order 0 and merges it with the existing binomial heap. In the union operation, the algorithm combines two binomial heaps by merging trees of the same order and carrying over any resulting trees, similar to binary addition. To find the minimum element, the algorithm traverses the root nodes of all binomial trees and returns the node with the smallest key value. Finally, the deletion operation involves decreasing the key value of the target node to negative infinity, extracting the minimum element, and then merging the remaining sub-trees with the original binomial heap. The binomial heap algorithm offers a significant advantage in terms of time complexity and performance, particularly in scenarios where merging heaps is a frequent operation.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.math
/**
* This calculates C(n,k). How many ways can k be chosen from n?
*/
fun binomial(n: Int, k: Int): Long {
var j = n - k + 1
var binomial = 1L
for (i in 1 until k + 1) {
binomial = binomial * j / i
j++
}
return binomial
}
