Unmanned aerial vehicles (UAVs) are widely usedas aerial base stations (BSs) to provide flexible connectivity andcoverage for ground users in various scenarios such as disasterrelief, traffic offloading, and so on. Especially, UAV deployment isan important issue that directly affects the coverage performanceof the UAV network. In this paper, we propose a novel heuristic algorithmbased three-dimensional (3-D) UAV deployment schemewhile guaranteeing the connectivity of the UAV network in bothstatic and dynamic user scenarios. For the static user scenario, weaim to deploy the minimum number of UAVs to provide coveragefor the users from the perspective of deployment cost. To reducethe deployment complexity, we decouple the 3-D UAV deploymentproblem from the vertical and horizontal dimensions. Specifically,we firstly determine the optimal vertical height of UAVs based onthe air-to-ground (A2G) model. Then, to alleviate the prematureconvergence of standard genetic algorithm (SGA), we designan improved genetic algorithm (IGA) to obtain the optimalhorizontal locations of UAVs. On this basis, when the users moveor increase, i.e., the dynamic user scenario, the already deployedUAVs cannot provide effective coverage. For this scenario, wepropose a UAV redeployment scheme to maximize the numberof covered users without increasing the number of UAVs. Tofurther reduce the cost of redeployment, we firstly modify theproposed IGA to obtain a feasible set of two-dimensional (2-D)redeployed locations of the UAVs. Then, we design a backtrackingalgorithm (BA) based UAV movement strategy to minimize thetotal flying distance of the UAVs. The simulation results showthat the effectiveness and convergence of our proposed schemes.