DEV Community: Mahibul Haque

An Intro to Heap Data Structure

Mahibul Haque — Fri, 03 Jun 2022 14:12:11 +0000

Topics that is going to be discussed-

Array Representation of BT
Complete Binary Tree
Heap
Insert & Delete
Heap Sort
Heapify
Priority Queue

Array Representation of Binary Tree

If a Node is at index -> i

It's left child is at -> 2*i
It's right child is at -> 2*i+1
It's parent is at -> i/2

If there are missing nodes in the Binary Tree, you need leave the corresponding index of the array blank.

Full Binary Tree V Complete Binary Tree:

So, the number of nodes of full binary tree is - (2^h+1)-1
Here, h is the height of the binary tree

Complete Binary Tree:

In a complete binary tree, if we traverse the binary tree in a level order fashion then we cannot have a missing node in between two nodes. So, a complete binary tree can be a full binary tree up until the binary tree's h-1.

Example of a not Complete binary tree in array representation

Height of a Complete Binary Tree will always be log(n)

Heap

Heap is a complete binary tree.

Min heap - Min heap is a complete binary tree satisfying the condition that each node is having the element smaller or equal to all its descendants.

Max heap - Min heap is a complete binary tree satisfying the condition that each node is having the element greater or equal to all its descendants.

Time taken for a insertion in a Heap-

minimum: O(1)
maximum: O(logn)
If you delete from a max-heap you will get the next largest element.
If you delete from a min-heap you will get the next smallest element.

Heap Sort:

Step-1: For a given set of elements create a heap.
Step-2: Delete all the elements one by one.

Hence, all the elements will be sorted.

Time Complexity for Heap Sort: O(nlogn)

Heapify:

While creating the heap in step-1 instead of going through the array from left to right, we go through it by going from right to left. You might wonder how this helps. If you recall heap element deletion procedure you will recall that the element that is to be deleted is sent to the bottom. We use that principle to build the heap in the heapify procedure. If a element does not have a children we just create the heap but if an element does posses children than we compare the children with parent and adjust the elements accordingly.

Time complexity for Heapify is O(n) which is better than the O(nlogn) time complexity we get by following the create heap procedure.

Priority Queue: In a priority queue elements should be deleted in the order of higher priority.

1.There can be two kinds priority - smaller number -> higher priority or larger number -> higher priority.

For smaller number -> higher priority you can use min-heap and for larger number -> higher priority you can use max-heap.

Since, insertion and deletion in a heap takes O(logn) time it is a great data structure for implementing priority queues.

An Idea about Blockchain

Mahibul Haque — Wed, 18 May 2022 13:59:46 +0000

What is Blockchain?

The generally accepted definition of a blockchain is a distributed ledger with smart contracts.
In business, whenever any object of value or important changes, it is captured in a transaction. Transactions therefore describe how a company's essential assets move through a lifecycle; for example, their movement between their suppliers and consumers in a supply chain.
Traditionally, transactions are recorded in a business ledger. Unfortunately, a transaction which involves multiple organizations will be recorded differently by each business. Business processes which would benefit from a consistent, up-to-date and high integrity ledger are adversely affected organizations with different ledgers and technology recording essentially the same transactions. For example, if two organizations disagree on the state of a transaction then a dispute occurs, which can often be costly and time-consuming to resolve. A shared ledger can also introduce new possibilities; real-time tracking and tracing of products becomes possible when all the participants in a supply chain have access to a trusted source of transactions.Blockchain transactions and ledgers are different. Blockchain introduces a new kind of transaction – a multiparty transaction - that is signed by everyone involved in the transaction. Blockchain ledgers are different too; the same ledger is replicated in every organization in the network, and kept synchronized using a process called consensus. Moreover, these ledgers are immutable and final; once a multi-party transaction is written to the ledger, it cannot be reversed.

Smart contracts

In business, transactions are generated according to contracts which define the exact conditions under which a transaction is generated. If I buy a car from you and it breaks down a month later, the terms of our contract might say that you are liable for the repair.

Blockchain introduces the idea of a smart contract. It describes in code what a transaction generated by the smart contract looks like. For example, a car contract might use logic to check that you're the current owner of the car, and that a purchaser has the required funds. If so, then a transaction will be generated that represents the transfer of the money to the seller and the car ownership to the buyer.

Blockchains such as Hyperledger Fabric make it easy to write smart contracts, by maintaining the current value of every business object in a ledger. It means that smart contracts don't need to compute the cumulative effect of the history of transactions that involve your car -- they simply look up the current state of that car, and modify it as required. Hyperledger Fabric makes it easy to capture these object changes as transactions and recorded on the distributed blockchain ledger.

Blockchain and Bitcoin

Blockchain is commonly associated with Bitcoin, the cryptocurrency and peer-to-peer payments system. Bitcoin uses a blockchain as the ledger to record its transactions and a resource-intensive method of consensus called proof of work. Bitcoin favors anonymity; even though the ledger is public, it's almost impossible to determine who is behind a Bitcoin transaction.

Businesses often have a different operating environment. For example, they are required to carry out Know Your Customer (KYC) and Anti-Money Laundering (AML) checks, which require businesses to know who they are dealing with. This means that business blockchains require identifiable participants and favor features such as privacy and confidentiality. Knowing who's behind a transaction helps to remove incentives for fraud and as such, resource-intensive methods of consensus are not needed.

And of course, business ledgers also store more than cryptocurrency transactions; any object of value to a business could be subject to multi-party transactions, and will therefore also benefit from a business blockchain.

What GraphQL Is and Isn't?

Mahibul Haque — Tue, 17 May 2022 09:44:11 +0000

Definition :

Graphql is a query language. But it does not mean it is a language that interacts with the database like popular SQL languages (e.g. MySQL, PostgresSQL).

So what does GraphQL do?
Queries an API, not a database.

Distinction between Query and Mutation in GraphQL

GraphQL doesn't require http requests method such as GET, POST, PUT, DELETE.

In GraphQL your most likely going to GET data by using Query. The other data update methods POST, PUT, DELETE will be handled by Mutations.

A query to fetch all the pets from the app might look like this:

query GetAllPets {
  pets {
    name
    petType
  }
}

And then a mutation that adds a new pet might look a little something like this:

mutation AddNewPet ($name: String!, $petType: PetType) {
  addPet(name: $name, petType: $petType) {
    id
    name
    petType
  }
}

GraphQL Vs REST

GraphQL	REST
GraphQL is an application layer server-side technology which is developed by Facebook for executing queries with existing data.	REST is a software architectural style that defines a set of constraints for creating Web services.
It follows client-driven architecture.	It follows server-driven architecture.
GraphQL can be organized in terms of a schema.	REST can be arranged in terms of endpoints.
GraphQL is a growing community.	REST is a large community.
The development speed in GraphQL is fast.	The development speed in REST is Slow.
The learning curve in GraphQL is difficult.	The learning curve in REST is moderate.
The identity is separated from how you fetch it.	The endpoint you call in REST is the identity of an object.
In GraphQL, the server determines available resources.	The shape and size of the resource are determined by the server in REST.
GraphQL provides high consistency across all platforms.	It is hard to get consistency across all platforms.
The message format for GraphQL mutations should be a string.	The message format for REST mutations can be anything.
It is strongly typed.	It is weakly typed.
GraphQL API endpoints are single.	REST API endpoints are multiple.
It uses metadata for query validation.	It does not have machine-readable metadata cacheable.
Provides consistent and high-quality UX across all operating systems.	It is difficult to get consistency across all operating systems.
Partners of GraphQL require API customization.	It offers flexible public API that can easily enable new applications.