“Heapsort” Kode Jawaban

Heapsort

# Heap Sort in python


  def heapify(arr, n, i):
      # Find largest among root and children
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
      # If root is not largest, swap with largest and continue heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
  
  def heapSort(arr):
      n = len(arr)
  
      # Build max heap
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          # Swap
          arr[i], arr[0] = arr[0], arr[i]
  
          # Heapify root element
          heapify(arr, i, 0)
  
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end='')
Bored Bat

Heapsort

#include<iostream>
#include<cmath>

using namespace std;

int find_min_element_index(int a[] , int element , int left_child , int right_child){
	if(a[element] <= a[left_child] && a[element] <= a[right_child])
		return element;

	if(a[left_child] <= a[element] && a[left_child] <= a[right_child])
		return left_child;

	if(a[right_child] <= a[element] && a[right_child] <= a[left_child])
		return right_child;
}

int check_heap(int a[] , int n){

	int second_last_level = (int)log2(n);

	int check_elements_upto_index = pow( 2 , second_last_level+1)-2;
	for(int i=0; i<=check_elements_upto_index; i++){

		if(2*i+1 <= n-1 || 2*i+2 <= n-1){
				if(2*i+1 <= n-1 && 2*i+2 <= n-1){
					if(a[i] <= a[2*i+1] && a[i] <= a[2*i+2])
					 	continue;
					else
						return 0;
				}
				else if(2*i+1 <= n-1){
						if(a[i] <= a[2*i+1])
							continue;
						else
							return 0;
				}
				else{
						if(a[i] <= a[2*i+2])
							continue;
						else
							return 0;
				}
			}
			else{
			   break;
			}
	}
	return 1;
}

void heapify(int a[] , int n){
	int heap_flag = 0;
	while(heap_flag == 0){
		int level = (int)log2(n);
		int ending_index_at_corresponding_level = pow(2 ,level+1)-2;
		for(int i = ending_index_at_corresponding_level;i >= 0 ;i--){
					if(2*i+1 <= n-1 || 2*i+2 <= n-1){
						if(2*i+1 <= n-1 && 2*i+2 <= n-1){
				                    int min_index = find_min_element_index(a , i , 2*i+1 , 2*i+2);
							 		if(min_index == i){
							 			continue;
									}
									else{
										int temp = a[min_index];
										a[min_index] = a[i];
										a[i] = temp;
									}
						}
						else if( 2*i+1 <= n-1){
								if(a[i] <= a[2*i+1])
									continue;
								else{
										int temp = a[i];
										a[i] = a[2*i+1];
										a[2*i+1] = temp;
									}
						}
						else{
								if(a[i] <= a[2*i+2])
									continue;
								else{
										int temp = a[i];
										a[i] = a[2*i+2];
										a[2*i+2] = temp;
								}
						}
					}
		}

		heap_flag = check_heap(a , n);
		if(heap_flag == 1){
			cout << a[0] <<", ";
			int temp = a[0];
			a[0] = a[n-1];
			a[n-1] = temp;
			n = n-1;
		}
		if(n==1){
			cout <<a[0] <<", ";
			break;
		}

		heap_flag = check_heap(a , n);
	}
}


int main(){
	int list[] = {6,8,7,9,1,4,3,2,5,0};
	cout<<endl<<"List of Elements before sort: ";
	for(int i = 0; i<10; i++)
        cout<<list[i]<<", ";
	cout <<endl<<endl<<"Sorted Output as Follows : ";
	heapify(list , 10);
	cout<<endl;
}
Grieving Gazelle

Heap Sort

package sort

type MaxHeap struct {
	slice    []Comparable
	heapSize int
	indices  map[int]int
}

func buildMaxHeap(slice0 []int) MaxHeap {
	var slice []Comparable
	for _, i := range slice0 {
		slice = append(slice, Int(i))
	}
	h := MaxHeap{}
	h.Init(slice)
	return h
}

func (h *MaxHeap) Init(slice []Comparable) {
	if slice == nil {
		slice = make([]Comparable, 0)
	}

	h.slice = slice
	h.heapSize = len(slice)
	h.indices = make(map[int]int)
	h.Heapify()
}

func (h MaxHeap) Heapify() {
	for i, v := range h.slice {
		h.indices[v.Idx()] = i
	}
	for i := h.heapSize / 2; i >= 0; i-- {
		h.heapifyDown(i)
	}
}

func (h *MaxHeap) Pop() Comparable {
	if h.heapSize == 0 {
		return nil
	}

	i := h.slice[0]
	h.heapSize--

	h.slice[0] = h.slice[h.heapSize]
	h.updateidx(0)
	h.heapifyDown(0)

	h.slice = h.slice[0:h.heapSize]
	return i
}

func (h *MaxHeap) Push(i Comparable) {
	h.slice = append(h.slice, i)
	h.updateidx(h.heapSize)
	h.heapifyUp(h.heapSize)
	h.heapSize++
}

func (h MaxHeap) Size() int {
	return h.heapSize
}

func (h MaxHeap) Update(i Comparable) {
	h.slice[h.indices[i.Idx()]] = i
	h.heapifyUp(h.indices[i.Idx()])
	h.heapifyDown(h.indices[i.Idx()])
}

func (h MaxHeap) updateidx(i int) {
	h.indices[h.slice[i].Idx()] = i
}

func (h MaxHeap) heapifyUp(i int) {
	if i == 0 {
		return
	}
	p := i / 2

	if h.slice[i].More(h.slice[p]) {
		h.slice[i], h.slice[p] = h.slice[p], h.slice[i]
		h.updateidx(i)
		h.updateidx(p)
		h.heapifyUp(p)
	}
}

func (h MaxHeap) heapifyDown(i int) {
	l, r := 2*i+1, 2*i+2
	max := i

	if l < h.heapSize && h.slice[l].More(h.slice[max]) {
		max = l
	}
	if r < h.heapSize && h.slice[r].More(h.slice[max]) {
		max = r
	}
	if max != i {
		h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
		h.updateidx(i)
		h.updateidx(max)
		h.heapifyDown(max)
	}
}

type Comparable interface {
	Idx() int
	More(interface{}) bool
}
type Int int

func (a Int) More(b interface{}) bool {
	return a > b.(Int)
}
func (a Int) Idx() int {
	return int(a)
}

func HeapSort(slice []int) []int {
	h := buildMaxHeap(slice)
	for i := len(h.slice) - 1; i >= 1; i-- {
		h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
		h.heapSize--
		h.heapifyDown(0)
	}

	res := []int{}
	for _, i := range h.slice {
		res = append(res, int(i.(Int)))
	}
	return res
}
gocrazygh

Heap Sort Name Arti

A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree.
Worried Wildebeest

Jawaban yang mirip dengan “Heapsort”

Jelajahi jawaban kode populer menurut bahasa

Jelajahi bahasa kode lainnya

Shell/Bash
C#
C++
C
CSS
HTML
Java
JavaScript
Objective-C
PHP
Python
Sql
Swift
Ruby
TypeScript
Go
Kotlin
Assembly
R
VBA
Scala
Rust
Dart
Elixir
Clojure
Haskell
Matlab
Erlang
Cobol
Fortran
Scheme
Perl
Groovy
Lua
Julia
Delphi
Abap
Lisp
Prolog
Pascal
ActionScript
Basic
Solidity
PowerShell
GDScript
Excel