heapsort
Heap sort
Heap sort is a sorting algorithm designed using the data structure of a heap. Heap sort is a selection sort. Its worst and best, The average time complexity is O(nlogn), which is also unstable sorting. First, let’s briefly understand the heap structure.
Heap
A heap is a complete binary tree with the following properties: the value of each node is greater than or equal to its left and right children The value of a node is called a big top heap; or the value of each node is less than or equal to the value of its left and right child nodes, which is called a small top heap.
Recommended courses: PHP Tutorial.
As shown below:
#At the same time, we number the nodes in the heap by layer and map this logical structure It looks like this in the array
The array is logically a heap structure. We use a simple formula to describe the definition of the heap:
Large top heap: arr[i] >= arr[2i 1] && arr[i] >= arr[2i 2]
Small top heap: arr[i]
The basic idea of heap sorting is:
Construct the sequence to be sorted into a big top Heap, at this time, the maximum value of the entire sequence is the root node at the top of the heap. Swap it with the last element, then the last value is the maximum value. Then reconstruct the remaining n-1 elements into a heap, so that the next smallest value of n elements will be obtained. If you execute this repeatedly, you can get an ordered sequence
The above is the detailed content of heapsort. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
What is the difference between heap and stack
Nov 22, 2022 pm 04:12 PM
Differences: 1. The heap space is generally allocated and released by the programmer; while the stack space is automatically allocated and released by the operating system. 2. The heap is stored in the second-level cache, and the life cycle is determined by the garbage collection algorithm of the virtual machine; while the stack uses the first-level cache, which is usually in the storage space when it is called, and is released immediately after the call is completed. 3. The data structures are different. Heap can be regarded as a tree, while stack is a first-in, last-out data structure.
Deque in Python: Implementing efficient queues and stacks
Apr 12, 2023 pm 09:46 PM
deque in Python is a low-level, highly optimized deque useful for implementing elegant and efficient Pythonic queues and stacks, which are the most common list-based data types in computing. In this article, Mr. Yun Duo will learn the following together with you: Start using deque to effectively pop up and append elements. Access any element in deque. Use deque to build an efficient queue. Start using deque to append elements to the right end of a Python list and pop up elements. The operations are generally very Efficient. If time complexity is expressed in Big O, then we can say that they are O(1). And when Python needs to reallocate memory to increase the underlying list to accept new elements, these
The difference between heap and stack
Jul 18, 2023 am 10:17 AM
The difference between heap and stack: 1. The memory allocation method is different. The heap is manually allocated and released by the programmer, while the stack is automatically allocated and released by the operating system. 2. The size is different. The size of the stack is fixed, while the stack is automatically allocated and released by the operating system. The size of is growing dynamically; 3. Data access methods are different. In the heap, data access is achieved through pointers, while in the stack, data access is achieved through variable names; 4. Data life cycle , In the heap, the life cycle of data can be very long, while in the stack, the life cycle of variables is determined by the scope in which they are located.
What are the differences between java heap and stack
Dec 25, 2023 pm 05:29 PM
The difference between Java heap and stack: 1. Memory allocation and management; 2. Storage content; 3. Thread execution and life cycle; 4. Performance impact. Detailed introduction: 1. Memory allocation and management. The Java heap is a dynamically allocated memory area, mainly used to store object instances. In Java, objects are allocated through heap memory. When an object is created, the Java virtual machine Allocate corresponding memory space on the system, and automatically perform garbage collection and memory management. The size of the heap can be dynamically adjusted at runtime, configured through JVM parameters, etc.
Heap and priority queue in C++
Aug 22, 2023 pm 04:16 PM
Heap and priority queue are commonly used data structures in C++, and they both have important application value. This article will introduce and analyze the heap and priority queue respectively to help readers better understand and use them. 1. Heap is a special tree data structure that can be used to implement priority queues. In the heap, each node satisfies the following properties: its value is not less than (or not greater than) the value of its parent node. Its left and right subtrees are also a heap. We call a heap that is no smaller than its parent node a "min-heap" and a heap that is no larger than its parent node a "max-heap"
PHP data structure: The secret of heap data structure, realizing efficient sorting and priority queue
Jun 01, 2024 pm 03:54 PM
The heap data structure in PHP is a tree structure that satisfies the complete binary tree and heap properties (the parent node value is greater/less than the child node value), and is implemented using an array. The heap supports two operations: sorting (extracting the largest element from small to large) and priority queue (extracting the largest element according to priority). The properties of the heap are maintained through the heapifyUp and heapifyDown methods respectively.
What are the usage scenarios of heap and priority queue in Python?
Oct 28, 2023 am 08:56 AM
What are the usage scenarios of heap and priority queue in Python? The heap is a special binary tree structure that is often used to efficiently maintain a dynamic collection. The heapq module in Python provides a heap implementation and can easily perform heap operations. A priority queue is also a special data structure. Unlike an ordinary queue, each element of it has a priority associated with it. The highest priority element is taken out first. The heapq module in Python can also implement the priority queue function. Below we introduce some
The concepts and applications of heap and stack in PHP
Jun 22, 2023 am 10:38 AM
As a very popular programming language, PHP plays a very important role in the processing and use of data structures. In PHP, heap and stack are two very important data structures, and they have important application value in program design and implementation. This article will introduce the heap and stack in PHP from both conceptual and application aspects. 1. The concepts of heap and stack Heap Heap is a data structure, which is a special tree structure. In PHP, a heap is a graph-like data structure composed of nodes and edges. Each node in the heap has a value, and each